A survey of wall-following algorithm for mobile robot

doi:10.16731/j.cnki.1671-3133.2024.02.020

Abstract

Abstract: The wall-following algorithm is a local path planning algorithm,and its global convergence is often better than other traditional methods.In order to promote the research of wall-following algorithm in the field of path planning,the latest progress and research results of mobile robots using wall-following algorithm to plan paths were reviewed.According to the obstacle avoidance strategy and implementation of wall-following algorithm,wall-following algorithm was divided into the wall-following algorithm based on the target direction angle,the wall-following algorithm based on M-Line,the wall-following algorithm based on the optimal obstacle avoidance direction,the wall-following algorithm based on historical information and the wall-following algorithm based on multi algorithm fusion,and the advantages and disadvantages of various algorithms were summarized.However,in the actual environment,due to the idealization of the simulation environment,the rigidity of the behavior cooperation mechanism,and the noise of sensors,there is a big gap between the wall-following algorithm in practical application and the theoretical results.Considering that there are still many shortcomings in the existing algorithms,the future development trend of the wall-following algorithm was prospected from three aspects,namely developing a wall-algorithm suitable for complex real environments,exploring a more efficient and reasonable multi-behavior switching mechanism and reducing the impact of sensor noise in real environments.

Key words: path planning, wall-following algorithm, mobile robot, unknown environment

CLC Number:

TP242

XU Sheng, SHA Xinmei, SU Ming. A survey of wall-following algorithm for mobile robot[J]. Modern Manufacturing Engineering, 2024, 521(2): 150-158.

References

[1] REN F,BAO Y.A review on human-computer interaction and intelligent robots[J].International Journal of Information Technology & Decision Making,2020,19(1):5-47.
[2] LAI R,LIN W.Review of research on the key technologies,application fields and development trends of intelligent robots[C]//International Conference on Intelligent Robotics and Applications.Newcastle,NSW,Australia:Springer,2018:449-458.
[3] MUHAMMAD A,ALI M A H,SHANONO I H.A review:on intelligent mobile robot path planning techniques[C]//11th IEEE Symposium on Computer Applications & Industrial Electronics.New York:IEEE,2021:53-58.
[4] MOHANTY P K,SINGH A K,KUMAR A,et al.Path planning techniques for mobile robots:a review[C]//Proceedings of the 13th International Conference on Soft Computing and Pattern Recognition.Innsbruck,Austria:[s.n.],2022:657-667.
[5] YAO T,HE T,ZHAO W,et al.Review of path planning for autonomous underwater vehicles[C]//Proceedings of the 2019 International Conference on Robotics,Intelligent Control and Artificial Intelligence.New York:[s.n.],2019:482-487.
[6] YUN X,TAN K C.A wall-following method for escaping local minima in potential field based motion planning[C]//1997 8th International Conference on Advanced Robotics.Monterey,CA,USA:IEEE,1997:421-426.
[7] LUMELSKY V,STEPANOV A.Dynamic path planning for a mobile automaton with limited information on the environment[J].IEEE Transactions on Automatic Control,1986,31:1058-1063.
[8] NOBORIO H.A path-planning algorithm for generation of an intuitively reasonable path in an unknown 2D workspace[C]//Proceedings of 1990 Japan-U.S.A.Symposium on Flexible Automation.[S.l.]:[s.n.],1990:477-480.
[9] KIM D H,SHIN K,HAN C S,et al.Sensor-based navigation of a car-like robot based on bug family algorithms[J].Proceedings of the Institution of Mechanical Engineers Part C-Journal of Mechanical Engineering Science,2013,227(C6):1224-1241.
[10] BORENSTEIN J,KOREN Y.Real-time obstacle avoidance for fast mobile robots[J].IEEE Transactions on Systems,Man and Cybernetics,1989,19:1179-1187.
[11] KANDATHIL J J,MATHEW R,HIREMATH S S.Development and analysis of a novel obstacle avoidance strategy for a multi-robot system inspired by the bug-1 algorithm[J].Simulation-Transactions of the Society for Modeling and Simulation International,2020,96(10):807-824.
[12] WANG M,LIU J N K.Fuzzy logic-based real-time robot navigation in unknown environment with dead ends[J].Robotics and Autonomous Systems,2008,56(7):625-643.
[13] JIANG J,TU D,XU S,et al.Cognitive response navigation algorithm for mobile robots using biological antennas[J].Robotica,2013,32:743-756.
[14] MOHSEN A M,SHARKAS M A,ZAGHLOL M S.New real time (m-bug) algorithm for path planning and obstacle avoidance in 2D unknown environment[C]//2019 29th International Conference on Computer Theory and Applications (ICCTA).Alexandria,Egypt:IEEE,2019:25-31.
[15] MARINO R,MASTROGIOVANNI F,SGORBISSA A,et al.A minimalistic quadrotor navigation strategy for indoor multi-floor scenarios[C]//Intelligent Autonomous Systems. Monterey:Springer,2016:1561-1570.
[16] ABAFOGI M,DURDU A,AKDEMIR B.A new approach to mobile robot navigation in unknown environments[C]//10th International Conference on Electronics,Computers and Artificial Intelligence.Singapore:IEEE,2018:1-5.
[17] HORIUCHI Y,NOBORIO H.Evaluation of path length made in sensor-based path-planning with the alternative following[C]//IEEE International Conference on Robotics and Automation.London,United Kingdom:IEEE,2001:1728-1735.
[18] LUMELSKY V J,SKEWIS T.Incorporating range sensing in the robot navigation function[J].IEEE Transactions on Systems,Man and Cybernetics,1990,20:1058-1069.
[19] YOO K,CHUN J.Analysis of optimal range sensor placement for tracking a moving target[J].IEEE Communications Letters,2020:18(2):145-149.
[20] SINGH M.Design and development of a low-cost laser range sensor[J].The Imaging Science Journal,2017,65:1-11.
[21] JUNG J W,PARK J S,KANEYAMA K,et al.Mobile robot path planning using a laser range finder for environments with transparent obstacles[J].Applied Sciences-Basel,2020,10(8):2799.
[22] 马晓辉,丁洪伟,王梦瑶,等.基于BUG理论的平行主线改进算法[J].实验科学与技术,2016,14(1):12-17.
[23] YUFKA A,PARLAKTUNA O.Performance comparison of bug algorithms for mobile robots[C]//5th International Advanced Technologies Symposium.Karabuk:Springer,2009.
[24] QUINONEZ Y,BARRERA Pincheira F,et al.Simulation and path planning for quadcopter obstacle avoidance in indoor environments using the ROS framework[C]//International Conference on Software Process Improvement.[S.l.]:IEEE,2018:295-304.
[25] SUN K,KUMAR V.Belief space planning for mobile robots with range sensors using ILQG[J].IEEE Robotics and Automation Letters,2021,6(2):1902-1909.
[26] KAMON I,RIMON E,RIVLIN E.A new range-sensor based globally convergent navigation algorithm for mobile robots[C]//Proceedings of the 1996 IEEE International Conference on Robotics and Automation.[S.l.]:[s.n.],1995:429-435.
[27] KAMON I,RIMON E,RIVLIN E.TangentBug:a range-sensor based navigation algorithm[J].International Journal of Robotic Research,1998,17:934-953.
[28] DIB L.E-bug:new bug path-planning algorithm for autonomous robot in unknown environment[C]//15 Proceedings of the International Conference on Intelligent Information Processing,Security and Advanced Communication.New York:ACM,2015:1-8.
[29] MISTRI A,DUTTA A.Automated navigation of a mobile robot using ultrasonic range sensor based on modified e-bug algorithm[C]//3rd International Conference on Energy and Power.[S.l.]:IEEE,2022:1-7.
[30] MAGID E,RIVLIN E.CautiousBug:a competitive algorithm for sensory-based robot navigation[C]//2004 IEEE/RSJ Intelligent Robots and Systems.Sendai,Japan:IEEE,2004,3:2757-2762.
[31] 徐望宝,张进.基于改进的CautiousBug算法的机器人局部路径规划[J].控制工程,2014,21(4):510-514.
[32] XU Q,TANG G.Vectorization path planning for autonomous mobile agent in unknown environment[J].Neural Computing & Applications,2013,23(7/8):2129-2135.
[33] GURUPRASAD K R.EgressBug:a real time path planning algorithm for a mobile robot in an unknown environment[C]//Proceedings of the 2011 international conference on Advanced Computing,Networking and Security.[S.l.]:IEEE,2011:228-236.
[34] GURUPRASAD K R.Egress:an online path planning algorithm for boundary exploration[C]//2012 IEEE International Conference on Robotics and Automation.[S.l.]:IEEE,2012:3991-3996.
[35] 朱毅,张涛,宋靖雁.未知环境下势场法路径规划的局部极小问题研究[J].自动化学报,2010,36(8):1122-1130.
[36] ZHU Y,ZHANG T,SONG L,et al.A new bug-type navigation algorithm for mobile robots in unknown environments containing moving obstacles[J].Industrial Robot-the International Journal of Robotics Research and Application,2012,39(1):27-39.
[37] ZHU Y,ZHANG T,SONG J,et al.A new bug-type navigation algorithm considering practical implementation issues for mobile robots[C]//2010 IEEE International Conference on Robotics and Biomimetics.Tianjin:IEEE,2010:531-536.
[38] 徐胜,邢强,王浩.解决势场法路径规划中局部极小问题的角度累积法[J].控制与决策,2022,37(8):1997-2007.
[39] 马家辰,张琦.基于多行为融合的移动机器人路径规划方法[J].北京理工大学学报,2014,34(6):576-581.
[40] 谭民,王硕.多机器人系统[M].北京:清华大学出版社,2005.
[41] 康亮,赵春霞.未知环境下改进的基于BUG算法的移动机器人路径规划[J].系统仿真学报,2009,21(17):5414-5422.
[42] NOBORIO H,MAEDA Y,URAKAWA K.Three or more dimensional sensor-based path-planning algorithm HD-I[C]//Proceedings 1999 IEEE/RSJ International Conference on Intelligent Robots and Systems.[S.l.]:IEEE,1999:1699-1706.
[43] HACENE N,MENDIL B.Fuzzy behavior-based control of three wheeled omnidirectional mobile robot[J].Interna-tional Journal of Automation and Computing,2019,16(2):163-185.
[44] 郭娜,李彩虹,王迪,等.结合预测和模糊控制的移动机器人路径规划[J].计算机工程与应用,2020,56(8):104-109.
[45] 魏立新,吴绍坤,孙浩,等.基于多行为的移动机器人路径规划[J].控制与决策,2019,34(12):2721-2726.
[46] XU Q L,TANG G,LIU H,et al.Radom intermediate points based path planning in unknown environment[J].Applied Mechanics and Materials,2013,325-326:1688-1691.
[47] XU Q L.RandomBug:novel path planning algorithm in unknown environment[J].The Open Electrical & Electronic Engineering Journal,2014,8:252-257.
[48] YE M,DONG X,ZHAO J,et al.Path planning of manipulator based on improved RRT^* algorithm[J].Journal of Physics:Conference Series,2022,2365:012038.
[49] 彭艳,鲍凌志,瞿栋,等.Multi-bug全局路径规划算法研究[J].农业机械学报,2020,51(6):375-384.
[50] XU Q,YU T,BAI J.The mobile robot path planning with motion constraints based on bug algorithm[C]//2017 Chinese Automation Congress.Jinan:IEEE,2017:2348-2352.
[51] HU Y,ZHANG Q,QIN L,et al.Escaping depressions in lrts with wall following method[C]//2017 Ninth International Conference on Intelligent Human-Machine Systems and Cybernetics.New York:IEEE,2017:134-138.
[52] SALAH A,SABATTO Z S.Development of behavior-based control systems for autonomous vehicle navigation[C]//World Congress on Industrial Control Systems Security.London,United Kingdom:Institute of Electrical and Electronics Engineers,2020:19-24.
[53] KHAZAEE M,SADEDEL M,DAVARPANAH A.Behavior-based navigation of an autonomous hexapod robot using a hybrid automaton[J].Journal of Intelligent & Robotic Systems,2021,102(2):29.