TY - JOUR

T1 - Reactive navigation of nonholonomic robots for search and tight circumnavigation of group objects through singular inter-object gaps

AU - Chernov, V.A.

AU - Matveev, A.S.

N1 - Export Date: 4 March 2024 CODEN: RASOE Адрес для корреспонденции: Matveev, A.S.; Department of Mathematics and Mechanics, Universitetskii 28, Petrodvoretz, Russian Federation; эл. почта: almat1712@yahoo.com Сведения о финансировании: Ministry of Education and Science of the Russian Federation, Minobrnauka, 075-10-2021-093, RAI-RND-2126 Текст о финансировании 1: This work was supported in part by the Ministry of Science and Higher Education of the Russian Federation (Project No. RAI-RND-2126 , Agreement 075-10-2021-093 ). Пристатейные ссылки: Haddal, C., Gertler, J., Homeland Security: Unmanned Aerial Vehicles and Border Surveillance (2010), p. 11; Behrje, U., Isokeit, C., Meyer, B., Ehlers, K., Maehle, E., AUV-based Quay Wall Inspection Using a Scanning Sonar-based Wall Following Algorithm (2022), OCEANS, Chennai; Yuh, J., Design and control of autonomous underwater robots: A survey (2000) Auton. Robots, 8 (1), pp. 7-24; Yu, H., Guo, C., Han, Y., Shen, Z., Bottom-following control of underactuated unmanned undersea vehicles with input saturation (2020) IEEE Access, 8; Lee, K., Han, M., Lane-following method for high speed autonomous vehicles (2008) Int. J. Automot. Technol., 9 (5), pp. 607-613; Matveev, A., Magerkin, V., Savkin, A., A method of reactive control for 3D navigation of a nonholonomic robot in tunnel-like environments (2020) Automatica, 114; Che, X., Zhang, Z., Sun, Y., Li, Y., Li, C., A Wall-Following Navigation Method for Autonomous Driving Based on Lidar in Tunnel Scenes (2022), pp. 594-598. , 2022 IEEE 25th International Conference on Computer Supported Cooperative Work in Design, CSCWD; Choset, H., Lynch, K., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L., Thrun, S., Principles of Robot Motion: Theory, Algorihms and Implementations (2005), MIT Press Englewood Cliffs and New Jersey; Matveev, A., Savkin, A., Hoy, M., Wang, C., Safe Robot Navigation Among Moving and Steady Obstacles (2016), Elsevier and Butterworth Heinemann Oxford, UK; Al-Mutib, K., Abdessemed, F., Faisal, M., Ramdane, H., Alsulaiman, M., Bencherif, M., Obstacle avoidance using wall-following strategy for indoor mobile robots (2016), 2nd IEEE International Symposium on Robotics and Manufacturing Automation, Rome; Beard, R., McLain, T., Goodrich, M., Anderson, E., Coordinated target assignment and intercept for unmanned air vehicles (2002) IEEE Trans. Robot. Autom., 18 (6), pp. 911-922; Kumar, R., Sawhney, H., Samarasekera, S., Hsu, S., Tao, H., Guo, Y., Hanna, K., Burt, P., Aerial video surveillance and exploitation (2001) Proc. IEEE, 89 (10), pp. 1518-1539; Tang, S., Shinzaki, D., Lowe, C., Clark, C., Multi-robot control for circumnavigation of particle distributions (2014) Distributed Autonomous Robotic Systems: Springer Tracts in Advanced Robotics, 104. , Springer Berlin; Zavlanos, M., Egerstedt, M., Pappas, G., Graph-theoretic connectivity control of mobile robot networks (2011) Proc. IEEE, 99 (9), pp. 1525-1540; IEEE Signal Processing Magazine, M., (2005) Special Issue: Location is Everything, , IEEE Press; Bishop, A., Fidan, B., Anderson, B., Doğancay, K., Pathirana, P., Optimality analysis of sensor-target localization geometries (2010) Automatica, 46 (3), pp. 479-492; Kamon, I., Rimon, E., Rivlin, E., Tangentbug: A range-sensor-based navigation algorithm (1998) Int. J. Robot. Res., 17, pp. 934-953; Silvestre, C., Cunha, R., Paulino, N., Pascoal, A., A bottom-following preview controller for autonomous underwater vehicles (2009) IEEE Trans. Control Syst. Technol., 17 (2), pp. 257-266; Ge, S., Lai, X., Mamun, A.A., Boundary following and globally convergent path planning using instant goals (2005) IEEE Trans. Syst. Man Cybern., 35 (2), pp. 1-15; Yang, K., Gan, S., Sukkarieh, S., An efficient path planning and control algorithm for RUAV's in unknown and cluttered environments (2010) J. Intell. Robot. Syst., 57 (1), pp. 101-122; Adhami-Mirhosseini, A., Yazdanpanah, M., Aguiar, A., Automatic bottom-following for underwater robotic vehicles (2014) Automatica, 50 (8), pp. 2155-2162; Bonin-Font, F., A, O., Oliver, G., Visual navigation for mobile robots: A survey (2008) J. Intell. Robot. Syst., 53, pp. 263-296; Güzel, M., Autonomous vehicle navigation using vision and mapless strategies: A survey (2013) Adv. Mech. Eng.; Qin, J., Li, M., Li, D., Zhong, J., Yang, K., A survey on visual navigation and positioning for autonomous UUVs (2022) Remote Sens., 14, p. 3794; Bemporad, A., Marco, M., Tesi, A., Sonar-based wall-following control of mobile robots (2000) ASME, J. Dyn. Syst. Meas. Control, 122, pp. 226-230; Zhu, Y., Zhang, T., Song, J., An improved wall following method for escaping from local minimum in artificial potential field based path planning (2009), pp. 6017-6022. , Proceedings of the 48th IEEE Conference on Decision and Control and the 28th Chinese Control Conference; Fazli, S., Kleeman, L., Wall following and obstacle avoidance results from a multi-DSP sonar ring on a mobile robot (2005), 1, pp. 432-437. , IEEE Int. Conf. Mech. Autom., Niagara Falls, Canada; Matveev, A., Teimoori, H., Savkin, A., A method for guidance and control of an autonomous vehicle in problems of border patrolling and obstacle avoidance (2011) Automatica, 47, pp. 515-524; Matveev, A.S., Hoy, M.C., Savkin, A.V., A Method for Reactive Navigation of Nonholonomic Robots in the Presence of Obstacles (2011), pp. 11894-11899. , 18th IFAC World Congress, Milano, Italy; Zhang, F., Justh, E.W., Krishnaprasad, P.S., Boundary following using gyroscopic control , 5, pp. 5204-5209. , Proceedings of the 43rd IEEE Conference on Decision and Control, (ISSN: 0191–2216) 2004; Zhang, F., Fratantoni, D.M., Paley, D.A., Lund, J.M., Leonard, N.E., Control of coordinated patterns for ocean sampling (2007) Internat. J. Control, 80 (7), pp. 1186-1199; Jia, H., Zhang, L., Bian, X., Yan, Z., Cheng, X., Zhou, J., A nonlinear bottom-following controller for underactuated autonomous underwater vehicles (2012) J. Cent. South Univ., 19 (5), pp. 1240-1248; Matveev, A., Wang, C., Savkin, A., Real-time navigation of mobile robots in problems of border patrolling and avoiding collisions with moving and deforming obstacles (2012) Robot. Auton. Syst., 60 (6), pp. 769-788; Yan, Z., Yu, H., Li, B., Bottom-following control for an underactuated unmanned undersea vehicle using integral-terminal sliding mode control (2015) J. Central South Univ., 22, pp. 4193-4204; Suwoyo, H., Tian, Y., Deng, C., Adriansyah, A., Improving a Wall-Following Robot Performance with a PID-Genetic Algorithm Controller (2018), pp. 314-318. , 2018 5th International Conference on Electrical Engineering, Computer Science and Informatics, EECSI; Wardana, A., Widyotriatmo, A., Suprijanto, A., Turnip, Wall following control of a mobile robot without orientation sensor (2013), pp. 212-215. , 2013 3rd International Conference on Instrumentation Control and Automation, ICA; Wei, X., Dong, E., Liu, C., Han, G., Yang, J., A wall-following algorithm based on dynamic virtual walls for mobile robots navigation (2017), pp. 46-51. , 2017 IEEE International Conference on Real-Time Computing and Robotics, RCAR; Juang, C., Hsu, C., Reinforcement ant optimized fuzzy controller for mobile-robot wall-following control (2009) IEEE Trans. Ind. Electron., 56 (10), pp. 3931-3940; Juang, C., Jhan, Y., Chen, Y., Hsu, C., Evolutionary wall-following hexapod robot using advanced multiobjective continuous ant colony optimized fuzzy controller (2018) IEEE Trans. Cogn. Dev. Syst., 10 (3), pp. 585-594; Arnold, V., The theory of singularities and its applications (1991), first ed. Cambridge University Press Cambridge; Arnold, V., Catastrophe theory (2004), third ed. Springer-Verlag NY; Fuhrmann, A., Sobottka, G., Distance fields for rapid collision detection in physically based modeling (2003); Lien, J., Thomas, S., Amato, N., A general framework for sampling on the medial axis of the free space (2003), 3, pp. 4439-4444. , 2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422); Sharir, M., Algorithmic motion planning (2004) Handbook of Discrete and Computational Geometry, , second ed; Lee, Y., Lengagne, S., Kheddar, A., Kim, Y., Accurate evaluation of a distance function for optimization-based motion planning (2012), pp. 1513-1518. , 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems; Breen, D., Mauch, S., Whitaker, R., Mao, J., 3D metamorphosis between different types of geometric models (2001) Comput. Graph. Forum, 20 (3), pp. 36-48; Osher, S., Fedkiw, R., Level set methods and dynamic implicit surfaces (2003) Applied Mathematical Sciences, 153. , Bloch A. Epstein C. Goriely A. Greengard L. Springer Berlin; Fisher, S., Lin, M., Fast penetration depth estimation for elastic bodies using deformed distance fields (2001), 1, pp. 330-336. , Proceedings 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems. Expanding the Societal Role of Robotics in the the Next Millennium (Cat. No.01CH37180), vol.1; Sethian, J., Evolution, implementation and application of level set and fast marching methods for advancing fronts (2001) J. Comput. Phys., 169, pp. 503-555; Claisse, A., Frey, P., Level set driven smooth curve approximation from unorganized or noisy point set (2009) European Series in Applied and Industrial Mathematics (ESAIM): Proceedings [electronic only], 27; Crandall, M., Ishii, H., Lions, P., User's guide to viscosity solutions of second order partial differential equations (1992) Bull. Amer. Math. Soc., 27, pp. 1-67; Mantegazza, C., Mennucci, A.C., Hamilton-Jacobi equations and distance functions on Riemannian manifolds (2003) Appl. Math. Optim., 47, pp. 1-25; Dubins, L., On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents (1957) Am. J. Math., 79, pp. 497-516; Chernov, V., Matveev, A., Geometric facts underlying algorithms of robot navigation for tight circumnavigation of group objects through singular inter-object gaps (2023), Online; arXiv; Kimmel, R., Sethian, J., Computing geodesic paths on manifolds (1998) Proc. Natl. Acad. Sci. USA, 95, pp. 8431-8435; Sethian, J., Fast matching methods (1999) SIAM Rev., 41; Strain, J., Fast tree-based redistancing for level set computations (1999) J. Comput. Phys., 152, pp. 664-686; Sussman, M., Fatemi, E., An efficient, interface-preserving level set redistancing algorithm and its applications to interfacial incompressible fluid flow (1999) SIAM J. Sci. Comput., 20, pp. 1165-1191; Zhao, H., A fast sweeping method for eikonal equations (2005) Math. Comp., 74, pp. 603-627; Qian, J., Zhang, Y., Zhao, H., Fast sweeping methods for eikonal equations on triangular meshes (2007) SIAM J. Numer. Anal., 45, pp. 83-107; Belyaev, A., Fayolle, P., An ADMM-based scheme for distance function approximation (2020) Numer. Algorithms, 84, pp. 983-996; Filippov, A., Differential Equations with Discontinuous Righthand Sides (1988), Kluwer Academic Publishers Dordrecht, the Netherlands; Yakubovich, V.A., Leonov, G.A., Gelig, A.K., Stability of Stationary Sets in Control Systems with Discontinuous Nonlinearities (2004), World Scientific Singapore; Delfour, M., Zolesio, J., Shape analysis via oriented distance function (1994) J. Funct. Anal., 124, pp. 129-201; Rockafellar, R.T., Convex Analysis (1970), Princeton University Press Princeton, NJ; Garrido, S., Moreno, L., Blanco, D., Munoz, M.L., Sensor-based global planning for mobile robot navigation (2007) Robotica, 25 (2), pp. 189-199; Fazli, S., Kleeman, L., Simultaneous landmark classification, localization and map building for an advanced sonar ring (2007) Robotica, 25 (3), pp. 283-296; Toibero, J., Carelli, R., Kuchen, B., Wall-following stable control for wheeled mobile robots (2006) IFAC Proc. Vol., 39 (15), pp. 85-90; McGuire, K.N., de Croon, G.C., Tuyls, K., A comparative study of bug algorithms for robot navigation (2019) Robot. Auton. Syst., 121; Clark, F., Optimization and Nonsmooth Analysis (1983), Wiley NYUR - https://www.scopus.com/inward/record.uri?eid=2-s2.0-85185509923&doi=10.1016%2fj.robot.2024.104649&partnerID=40&md5=de0812432efb30bf733e7dbc86030982

PY - 2024/4/1

Y1 - 2024/4/1

N2 - An underactuated nonholonomic Dubins-vehicle-like robot with a lower-limited turning radius travels with a constant speed in a plane, which hosts unknown complex objects. In its local frame, the robot has sensorial access only to the part of the scene that is within a finite zone of visibility and in direct line of sight. It is required to approach and then circumnavigate the objects, with maintaining a given distance to the currently nearest of them, so that the ideal targeted path is the equidistant curve of the set of the objects. The focus is on the case where this curve cannot be perfectly traced due to excessive contortions and singularities. So the objective is restated as that of automatically finding, approaching and repeatedly tracing an approximation of the equidistant curve that is the best among those trackable by the robot with respecting safety concerns. Though pre-computation of this approximation is a hard problem of computational geometry, we show that autonomously seeking and tracking this approximation can be performed on-the-fly at a miserable computational cost via implementation of the proposed navigation law. This law is hybrid and operates in only a few discrete modes; within any mode, it is reactive, i.e., it directly converts the current observation into the current control. Nonlocal convergence of this law is justified by mathematically rigorous results and is confirmed by computer simulations and real-world experiments. © 2024 Elsevier B.V.

AB - An underactuated nonholonomic Dubins-vehicle-like robot with a lower-limited turning radius travels with a constant speed in a plane, which hosts unknown complex objects. In its local frame, the robot has sensorial access only to the part of the scene that is within a finite zone of visibility and in direct line of sight. It is required to approach and then circumnavigate the objects, with maintaining a given distance to the currently nearest of them, so that the ideal targeted path is the equidistant curve of the set of the objects. The focus is on the case where this curve cannot be perfectly traced due to excessive contortions and singularities. So the objective is restated as that of automatically finding, approaching and repeatedly tracing an approximation of the equidistant curve that is the best among those trackable by the robot with respecting safety concerns. Though pre-computation of this approximation is a hard problem of computational geometry, we show that autonomously seeking and tracking this approximation can be performed on-the-fly at a miserable computational cost via implementation of the proposed navigation law. This law is hybrid and operates in only a few discrete modes; within any mode, it is reactive, i.e., it directly converts the current observation into the current control. Nonlocal convergence of this law is justified by mathematically rigorous results and is confirmed by computer simulations and real-world experiments. © 2024 Elsevier B.V.

KW - Boundary following

KW - Mobile robots

KW - Motion control

KW - Navigation

KW - Nonholonomic constraints

KW - Path Singularities

KW - Computational geometry

KW - Constant speed

KW - Equidistant curves

KW - Non holonomic constraint

KW - Non-holonomic robot

KW - Nonholonomics

KW - Path singularity

KW - Reactive navigation

KW - Turning radius

KW - Underactuated

UR - https://www.mendeley.com/catalogue/bebfed82-77ac-36f4-a6d8-945d340e90b6/

U2 - 10.1016/j.robot.2024.104649

DO - 10.1016/j.robot.2024.104649

M3 - статья

VL - 174

JO - Robotics and Autonomous Systems

JF - Robotics and Autonomous Systems

SN - 0921-8890

M1 - 104649

ER -