Quadrant based incremental planning for mobile robots

Abstract

Path planning of a mobile robot in the presence of multiple moving obstacles is found to be a complicated problem. A planning algorithm capable of negotiating both static and moving obstacles in an unpredictable (on-line) environment is proposed. The proposed incremental algorithm plans the path by considering the quadrants in which the current positions of obstacles as well as target are situated. Also, the governing equations for the shortest path are derived. The proposed mathematical model describes the motion (satisfying constraints of the mobile robot) along a collision-free path. Further, the algorithm is applicable to dynamic environments with fixed or moving targets. Simulation results show the effectiveness of the proposed algorithm. Comparison of results with the improved artificial potential field (iAPF) algorithm shows that the proposed algorithm yields shorter path length with less computation time.

Keywords

mobile robots / incremental planning / quadrant based approach / dynamic environment

References

[1] RajaP, PugazhenthiS. On-line path planning for mobile robots in dynamic environments [J]. Neural Network World, 2012, 22(1): 67-83

[2] Elizondo-LealJ C, Parra-GonzálezE F, Ramírez-TorresJ G. The exact Euclidean distance transform: A new algorithm for universal path planning [J]. International Journal of Advanced Robotic Systems, 2013, 10(266): 1-10

[3] OhkiT, NagataniK, YoshidaK. Local path planner for mobile robot in dynamic environment based on distance time transform method [J]. Advanced Robotics, 2012, 26(14): 1623-1647

[4] LikhachevM, FergusonD, GordonG, StentzA, ThrunS. Anytime dynamic A*: An any-time, replanning algorithm [C]. Proc 2005 Int Conf on Automated Planning and Scheduling. Monterey, 2005262-271

[5] PaytonD W, RosenblattJ K, KeirseyD M. Grid-based mapping for autonomous mobile robot [J]. Robotics and Autonomous Systems, 1993, 11(1): 13-21

[6] RajaP, PugazhenthiS. Path planning for a mobile robot using real coded genetic algorithm [J]. International Journal of Assistive Robotics and Systems, 2009, 10(1): 27-39

[7] MitchellH. An algorithmic approach to some problems in terrain navigation [J]. Artificial Intelligence, 1988, 37(1): 171-201

[8] DunlaingC O, YapC K. A retraction method for planning the motion of a disc [J]. Journal of Algorithms, 1985, 6: 104-111

[9] ArkinR C. Navigational path planning for a vision-based mobile robot [J]. Robotica, 1989, 7(1): 49-63

[10] MohajerB, KianiK, SamieiE, SharifiM. A new online random particles optimization algorithm for mobile robot path planning in dynamic environments [J]. Mathematical Problems in Engineering, 2013, 2013: 1-9

[11] MinH Q, ZhuJ H, ZhengX J. Obstacle avoidance with multi-objective optimization by PSO in dynamic environment [C]. Proc IEEE Int Conf on Machine Learning and Cybernetics. Guangzhou, 20052950-2956

[12] YahjaA, SinghS, StentzA. An efficient on-line path planner for outdoor mobile robots [J]. Journal of Robotics and Autonomous Systems, 2000, 32(2/3): 129-143

[13] Al-TaharwaI, ShetaA, Al-WeshahM. A mobile robot path planning using genetic algorithm in static environment [J]. Journal of Computer Science, 2008, 4(4): 341-344

[14] PradoM, SimonA, CarabiasE, PerezA, EzquerroF. Optimal velocity planning of wheeled mobile robots on specific paths in static and dynamic environments [J]. Journal of Robotic Systems, 2003, 20(12): 737-754

[15] BuniyaminN, WanngahW A J, SariffN, MohamadZ. A simple local path planning algorithm for autonomous mobile robots [J]. International Journal of Systems Applications, Engineering & Development, 2011, 5(2): 151-159

[16] ChakravarthyA, GhoseD. Obstacle avoidance in a dynamic environment: A collision cone approach [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 1998, 28(5): 562-574

[17] ChazelleBSchwartzJ T, YapC K. Approximation and decomposition of shapes [M]. Advances in Robotics: Algorithmic and geometric aspects of robotics, 1987, Hillsdale, NJ, Lawrence Erlbaum: 145-185

[18] O’RourkeJ, BadlerN. Decomposition of three-dimensional objects into spheres [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1979, 1(3): 295-305

[19] ZengL, BoneG M. Mobile robot collision avoidance in human environments [J]. International Journal of Advanced Robotic Systems, 2013, 10(41): 1-14

[20] LuY, YiX-y, ChengJ-lin. A new potential field method for mobile robot path planning in the dynamic environments [J]. Asian Journal of Control, 2009, 11: 214-225

[21] LengC, CaoQ, HuangY. A motion planning method for Omni-directional mobile robot based on the anisotropic characteristics [J]. International Journal of Advanced Robotic Systems, 2008, 5(4): 327-340

[22] RajaP, PugazhenthiS. Path planning for a mobile robot to avoid polyhedral and curved obstacles [J]. International Journal of Assistive Robotics and Mechatronics, 2008, 9(2): 31-41

[23] RajaP, PugazhenthiS. Path planning for mobile robots in dynamic environments using particle swarm optimization [C]. Proc 2009 Int Conf on Advances in Recent Technologies in Communication and Computing. Kottayam, 2009401-405

[24] RajaP, PugazhenthiS. Path planning for a mobile robot in dynamic environments [J]. International Journal of Physical Sciences, 2011, 6(20): 4721-4731

[25] RajaP, PugazhenthiS. Optimal path planning of mobile robots: A review [J]. International Journal of Physical Sciences, 2012, 7(9): 1314-1320