Mobile Robot Motion Using Cellular Automaton Model to Avoid Transient Obstacles

Full Text (PDF, 691KB), PP.73-80

Views: 0 Downloads: 0


Kohei Arai 1,* Steven Ray Sentinuwo 1

1. Faculty of Science and Engineering, SAGA University, Saga, 840-8502 Japan

* Corresponding author.


Received: 10 May 2013 / Revised: 2 Jun. 2013 / Accepted: 4 Jul. 2013 / Published: 8 Aug. 2013

Index Terms

Mobile Robot Motion, Cellular Automaton Model, Transient Obstacle Avoidance


The obstacle avoidance is currently treated by methods that fall into two broad categories: global and local approach. This paper considers the obstacles whose velocity and direction cannot be easily predicted. Such obstacle is called transient obstacle. To avoid such kind of obstacle, we introduce a local path planning method for a robotics by using cellular automaton approach. The cellular automaton was combined with Dijkstra shortest path algorithm as global path planning to obtain a path for mobile robot to be able to avoid transient obstacle along the path. Using the proposed method, a scene in a typical corridor has been created. Moreover, this paper also evaluated two kinds of obstacle avoidance motion. First, the robot uses the “stop and go” method, which is the robot decreases its speed while encounter a transient obstacle. The second one is detour method, in which the robot makes a detour motion to avoid a transient obstacle. To coupe the drawbacks of local path planning, this paper also propose the enhancement of detour method. The simulation results show that in dynamic environment with transient obstacles, the “stop and go” method produces minimal collision with shortest-distance path. While, using the detour method generates minimal collision with time-minimal navigation path.

Cite This Paper

Kohei Arai, Steven Ray Sentinuwo, "Mobile Robot Motion Using Cellular Automaton Model to Avoid Transient Obstacles", International Journal of Modern Education and Computer Science (IJMECS), vol.5, no.8, pp.73-80, 2013. DOI:10.5815/ijmecs.2013.08.08


[1]P. Fiorini and Z. Shiller, “Motion planning in dynamic environments using velocity obstacles,” The International Journal of Robotics Research 17(7), 1998.
[2]J. Reif and M. Sharir, “Motion planning in the presence of moving obstacles,” J. ACM 41(4), 1994.
[3]K. Fujimura and H. Samet, “Planning a time-minimal motion among moving obstacles,” Algorithmica 10, 1993.
[4]K. Fujimura, “Motion planning amid transient obstacles,” The International Journal of Robotics Research, MIT, 1994.
[5]A. Elfes, “Sonar-based real-world mapping and navigation,” IEEE Journal of Robotics and Automation, 1987.
[6]J. Barraquand, B. Langlois, and J. C. Latombe, “Numerical potential field techniques for robot path planning,” IEEE, Transactions on System, Man and Cybernetics, 1992.
[7]Y. Hwang and N. Ahuja, “A potential field approach to path planning,” IEEE Transactions on Robotics and Automation, 1992.
[8]O. Khatib, “Real time obstacle avoidance for manipulator and mobile robots,” International Journal of Robotics Research 5(1), 1986.
[9]N. Amato and Y. Wu, “A randomized roadmap for path manipulation planning,” IEEE, International Conference on Robotics and Automation, 1996.
[10]L. E. Kavraki and J. C. Latombe, “Randomized preprocessing of configurations space for path planning,” IEEE, International Conference on Robotics and Automation, 1994.
[11]J. Borenstein and Y. Koren, “The vector field histogram – fast obstacle avoidance for mobile robots,” Robotics and Automation, IEEE Transactions, Vol. 7 (3), 1991.
[12]L. Sun, R. Lin, W. Wang, and Z. Du, “Mobile robot real-time path planning based on virtual targets method,” 2011 Third International Conference on Measuring Technology and Mechatronics Automation, IEEE, 2011.
[13]D. E. Goldberg, “Genetic and evolutionary algorithms come on age,” Communications ACM, 1994.
[14]M. Dorigo and T. Stutzle, “Ant colony optimization,” London, England, MIT Press Cambridge, Masachusetts, 2004.
[15]N. Buniyamin, N. Sariff, W. A. J. Wan Ngah, and Z. Mohamad, “Robot global path planning overview and a variation of ant colony system algorithm,” International Journal of Mathematics and Computers in Simulation Vol.5, 2011.
[16]Y. Eberhart and Shi, “Particle swarm optimization: developments, applications and resources in evolutionary computation,” Proceedings of the 2001 Congress on Evolutionary Computation, 2001.
[17]H. S. Kamran, A. Kaveh, W. M. Theodore, L. Roger, and T. Heng-M, “Autonomous local path planning for a mobile robot using a genetic algorithm,” Proceedings of the IEEE Congress on Evolutionary Computation 2004, pp. 1338-1344, 2004.
[18]T. Arai, J. Ota, E. Yoshida, and D. Kurabayashi, “Acquisition and utilization of motion skills in motion planning of multiple robots,” IEEE International Conference on Systems, Man and Cybernetics, 1995.
[19]T. Ishikawa, Y. Nishimura, and K. Hori, “Real-time collision avoidance in the environment with moving obstacle,” IEEE CIMCA, 2008.
[20]C. W. Lim, S. Y. Lim, and M. H. Ang Jr., “Hybrid of global path planning and local navigation implemented on a mobile robot in indoor environment,” Proceedings of the 2002 IEEE International Symposium on Intelligent Control (2002): 821‑826, United States: IEEE, 2002.
[21]J. Von Neumann and A. W. Burks,” Theory of self-reproducing automata,” Urbana, University of Illinois Press, 1966.
[22]J. Reif and M. Sharir, “Motion planning in the presence of moving obstacles,” J. ACM 41(4), 1994.
[23]C. Burstedde, K. Klauck, and A. Schadschneider, “Simulation of pedestrian dynamics using a two-dimensional cellular automaton,” Physica A, 2001.