A Navigation System for Autonomous Robot Operating in Unknown and Dynamic Environment: Escaping Algorithm

Document Type: Original Article

Authors

Faculty of Electrical Engineering, K. N. Toosi Univ. of Technology, Tehran, Iran

Abstract

In this study, the problem of navigation in dynamic and unknown environment is investigated and a navigation method based on force field approach is suggested. It is assumed that the robot performs navigation in unknown environment and builds the map through SLAM procedure. Since the moving objects' location and properties are unknown, they are identified and tracked by Kalman filter. Kalman observer provides important information about next paths of moving objects which are employed in finding collision point and time in future. In the time of collision detection, a modifying force is added to repulsive and attractive forces corresponding to the static environment and leads the robot to avoid collision. Moreover, a safe turning angle is defined to assure safe navigation of the robot. The performance of proposed method, named Escaping Algorithm, is verified through different simulation and experimental tests. Besides, comparison between Escaping Algorithm and Probabilistic Velocity Obstacle, based on computational complexity and required steps for finishing the mission is provided in this paper. The results show Escaping Algorithm outperforms PVO in term of dynamic obstacle avoidance and complexity as a practical method for autonomous navigation




Abstract—In this study, the problem of navigation in dynamic and unknown environment is investigated and a navigation method based on force field approach is suggested. It is assumed that the robot performs navigation in unknown environment and builds the map through SLAM procedure. Since the moving objects' location and properties are unknown, they are identified and tracked by Kalman filter. Kalman observer provides important information about next paths of moving objects which are employed in finding collision point and time in future. In the time of collision detection, a modifying force is added to repulsive and attractive forces corresponding to the static environment and leads the robot to avoid collision. Moreover, a safe turning angle is defined to assure safe navigation of the robot. The performance of proposed method, named Escaping Algorithm, is verified through different simulation and experimental tests. Besides, comparison between Escaping Algorithm and Probabilistic Velocity Obstacle, based on computational complexity and required steps for finishing the mission is provided in this paper. The results show Escaping Algorithm outperforms PVO in term of dynamic obstacle avoidance and complexity as a practical method for autonomous navigation.

[1] A. Ferworn, J. Tran, A. Ufkes, and A. D’Souza, “Initial experiments on 3d modeling of complex disaster environments using unmanned aerial vehicles,” in Safety, Security, and Rescue Robotics (SSRR), 2011 IEEE International Symposium on. IEEE, 2011, pp. 167–171.

[2]    K. Nagatani, S. Kiribayashi, Y. Okada, K. Otake, K. Yoshida, S. Tadokoro, T. Nishimura, T. Yoshida, E. Koyanagi, M. Fukushima et al., “Emergencyresponse to the nuclear accident at the fukushimadaiichi nuclear power plants using mobile rescue robots,” Journal of Field Robotics, 2012.

[3]    X. Lai, S. Ge, and A. Al Mamun, “Hierarchical incremental path planning and situation-dependent optimized dynamic motion planning consideringaccelerations,” Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, vol. 37, no. 6, pp. 1541–1554, 2007.

[4]    G. Oriolo, G. Ulivi, and M. Vendittelli, “Real-time map building and navigation for autonomous robots in unknown environments,” Systems, Man, andCybernetics, Part B: Cybernetics, IEEE Transactions on, vol. 28, no. 3, pp. 316–333, 1998.

[5]    O. Khatib, “Real-time obstacle avoidance for manipulators and mobile robots,” The international journal of robotics research, vol. 5, no. 1, pp. 90–98,1986.

[6]    Y. Lu, X. Huo, O. Arslan, and P. Tsiotras, “Incremental multi-scale search algorithm for dynamic path planning with low worst-case complexity,” Systems,Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, vol. 41, no. 6, pp. 1556– 1570, 2011.

[7]    A. Yahja, S. Singh, and A. Stentz, “An efficient on-line path planner for outdoor mobile robots,” Robotics and Autonomous systems, vol. 32, no. 2, pp.129–143, 2000.

[8]    L. B. Cremean, T. B. Foote, J. H. Gillula, G. H. Hines, D. Kogan, K. L. Kriechbaum, J. C. Lamb, J. Leibs, L. Lindzey, C. E. Rasmussen et al., “Alice:An information-rich autonomous vehicle for high-speed desert navigation,” Journal of Field Robotics, vol. 23, no. 9, pp. 777–810, 2006.

[9]    D. Fox, W. Burgard, and S. Thrun, “The dynamic window approach to collision avoidance,” Robotics & Automation Magazine, IEEE, vol. 4, no. 1, pp.23–33, 1997.

[10]  N. A. Melchior, J.-y. Kwak, and R. Simmons, “Particle rrt for path planning in very rough terrain,” in NASA Science Technology Conference 2007 (NSTC2007). Citeseer, 2007.

[11] G. Chen and T. Fraichard, “A real-time navigation architecture for automated vehicles in urban environments,” in Intelligent Vehicles Symposium, 2007IEEE. IEEE, 2007, pp. 1223–1228.

[12] P. Fiorini and Z. Shiller, “Motion planning in dynamic environments using velocity obstacles,” The International Journal of Robotics Research, vol. 17,no. 7, pp. 760–772, 1998.

[13] C. Fulgenzi, A. Spalanzani, and C. Laugier, “Dynamic obstacle avoidance in uncertain environment combining pvos and occupancy grid,” in Robotics and Automation, 2007 IEEE International Conference on. IEEE, 2007, pp. 1610–1616.

[14] B. Kluge and E. Prassler, “Recursive probabilistic velocity obstacles for reflective navigation,” in Field and Service Robotics. Springer, 2006, pp. 71–79.

[15] T. Fraichard and H. Asama, “Inevitable collision statesa step towards safer robots?” Advanced Robotics, vol. 18, no. 10, pp. 1001–1024, 2004.

[16] T. Fraichard, “A short paper about motion safety,” in Robotics and Automation, 2007 IEEE International Conference on. IEEE, 2007, pp. 1140–1145.

[17] A. Bautin, L. Martinez-Gomez, and T. Fraichard, “Inevitable collision states: a probabilistic perspective,” in Robotics and Automation (ICRA), 2010IEEE International Conference on. IEEE, 2010, pp. 4022–4027.

[18] J. Borenstein and Y. Koren, “Real-time obstacle avoidance for fact mobile robots,” Systems, Man and Cybernetics, IEEE Transactions on, vol. 19, no. 5,pp. 1179–1187, 1989.

[19] J. Chuang and N. Ahuja, “An analytically tractable potential field model of free space and its application in obstacle avoidance,” Systems, Man, andCybernetics, Part B: Cybernetics, IEEE Transactions on, vol. 28, no. 5, pp. 729–736, 1998.

[20]  E. Rimon and D. Koditschek, “Exact robot navigation using artificial potential functions,” Robotics and Automation, IEEE Transactions on, vol. 8, no. 5,pp. 501–518, 1992.

[21]  J. Kim and P. Khosla, “Real-time obstacle avoidance using harmonic potential functions,” Robotics and Automation, IEEE Transactions on, vol. 8, no. 3,pp. 338–349, 1992.

[22] P. Veelaert and W. Bogaerts, “Ultrasonic potential field sensor for obstacle avoidance,” Robotics and Automation, IEEE Transactions on, vol. 15, no. 4,pp. 774–779, 1999.

[23]        N. Ko and B. Lee, “Avoidability measure in moving obstacle avoidance problem and its use for robot motion planning,” in Intelligent Robots and Systems’ 96, IROS 96, Proceedings of the 1996 IEEE/RSJ International Conference on, vol. 3. IEEE, 1996, pp. 1296–1303.

[24]         S. Ge and Y. Cui, “Dynamic motion planning for mobile robots using potential field method,” Autonomous Robots, vol. 13, no. 3, pp. 207–222, 2002.

[25]        L. Huang, “Velocity planning for a mobile robot to track a moving target–a potential field approach,” Robotics and Autonomous Systems, vol. 57, no. 1, pp. 55–63, 2009.

[26]        G. Grisetti, C. Stachniss, and W. Burgard, “Improved techniques for grid mapping with rao-blackwellized particle filters,” Robotics, IEEE Transactions on, vol. 23, no. 1, pp. 34–46, 2007.

[27]        S. Ge and Y. Cui, “New potential functions for mobile robot path planning,” Robotics and Automation, IEEE Transactions on, vol. 16, no. 5, pp. 615–620, 2000.

[28]        L. Montesano, J. Minguez, and L. Montano, “Modeling dynamic scenarios for local sensor-based motion planning,” Autonomous Robots, vol. 25, no. 3, pp. 231–251, 2008.

[29]         S. Thrun, C. Martin, Y. Liu, D. Hahnel, R. Emery-Montemerlo, D. Chakrabarti, and W. Burgard, “A real-time expectation-maximization algorithm for acquiring multiplanar maps of indoor environments with mobile robots,” Robotics and Automation, IEEE Transactions on, vol. 20, no. 3, pp. 433–443, 2004.

[30]        G. McLachlan and T. Krishnan, The EM algorithm and extensions. Wiley New York, 1997, vol. 274.

[31]         I. Cox, “A review of statistical data association techniques for motion correspondence,” International Journal of Computer Vision, vol. 10, no. 1, pp.                53–66, 1993.

[32]        M. Lindstrom and J. Eklundh, “Detecting and tracking moving objects from a mobile platform using a laser range scanner,” in Intelligent Robots and Systems, 2001. Proceedings. 2001 IEEE/RSJ International Conference on, vol. 3. IEEE, 2001, pp. 1364–1369.

[33]        V. Petridis and T. Tsiboukis, “An optimal solution to the robot navigation planning problem based on an electromagnetic analogue,” Robotic systems: advanced techniques and applications, vol. 10, pp. 297–303, 1992.

[34]         P. Besl and N. McKay, “A method for registration of 3-d shapes,” IEEE Transactions on pattern analysis and machine intelligence, vol. 14, no. 2, pp. 239–256, 1992.

[35] F Adib Yaghmaie, A Mobarhani, HD Taghirad, “A new method for mobile robot navigation in dynamic environment: Escaping algorithm”, in IEEE Robotics and Mechatronics (ICRoM), 2013 First RSI/ISM International Conference on, pp. 212-217.