Path Planing for Mobile Robot With Cellular Automata

Judhi Santoso, Bambang Riyanto, Setiono Santoso


In this paper we propose a new approach, the robot path planning with cellular automata. The idea is based on maximum clearence technique that preserves the distance of the robot toobstacles as far as possible. An existing approach is implemented using voronoi diagram thatgenerates the candidate paths that are safe from collision with the obstacles. In fact, maximum clearence method can be solved analitically using the deformation retraction, but this approach is applicable for the continuous environment only and it requires a lot offunction computation. Hence, we solve this problem using a particular rule of cellular automata to perform the process of computation that can be done efficiently. Our approach is suitable for path planning in a grid-based environtment.

Full Text:



S. Thrun. Robotic mapping: A survey. In G. Lakemeyer and B. Nebel, editors, Exploring Artificial Intelligence in the New Millenium. Morgan Kaufmann, 2002. to appear.

I. P. Androulakis. Dynamic programming: Stochastic shortest path problems. In Encyclopedia of Optimization, pages 869–873. 2009.

N. T. Moungla, L. Létocart, and A. Nagih. An improving dynamic programming algorithm to solve the shortest path problem with time windows. Electronic Notes in Discrete Mathematics, 36:931–938, 2010.

F. Bagnoli. Cellular Automata. ArXiv Condensed Matter e-prints, oct 1998.

M. Mitchell. Computation in cellular automata: A selected review. In Nonstandard Computation, pages 95–140. Wiley-VCH, 1996.

J. Santoso, O. S. Santoso, and B. R. Trilaksono. Matrix characteristics for two dimensional nongroup cellular automata. In Proceedings of the 2011 International Conference on Electrical Engineering and Informatics, pages K2–4, Bandung, July 2011. IEEE.

S. Wolfram. A new kind of science. Wolfram Media, 2002.

C. Behring, M. Bracho, M. Castro, and J. A. Moreno. An algorithm for robot path planning with cellular automata. In ACRI, pages 11–19, 2000.

Y. Tavakoli, H. S. Javadi, and S. Adabi. A Cellular Automata Based Algorithm for Path Planning in Multi-Agent Systems with A Common Goal. International Journal of Computer Science and Network Security, 8(7):119–123, 2008.

F. M. Marchese. A path-planner for mobile robots of generic shape with multilayered cellular automata. In ACRI, pages 178–189, 2002.

S. Garrido, L. Moreno, M. Abderrahim, and F. M. Monar. Path planning for mobile robot navigation using voronoi diagram and fast marching. In IROS, pages 2376–2381, 2006.

K. Ioannidis, G. C. Sirakoulis, and I. Andreadis. A path planning method based on cellular automata for cooperative robots. Applied Artificial Intelligence, 25(8):721–745, 2011.

M. A. Mansor and A. S. Morris. Path planning in unknown environment with obstacles using virtual window. Journal of Intelligent and Robotic Systems, 24(3):235–251, 1999.

T. L. Chien, H. C. Lai, Y. C. Lin, and Y. C. Lin. Dynamic

programming algorithm based path planning of the multiple robot system. In ICDMA, pages 469–474, 2011.

A. Pal, R. Tiwari, and A. Shukla. A focused wave front algorithm for mobile robot path planning. In HAIS (1), pages 190–197, 2011.

J. Santoso, O. S. Santoso, and B. R. Trilaksono. Dynamic robot path planning with cellular automata. In Proceedings of the 8th International Conference on Intelligent Unmanned Systems, ISBN: 978-981-07-4225-6, pages 179-183, Singapore, October 2012. SIM University, Research Publishing.

V. Desaraju and J. P. How. Decentralized path planning for multi-agent teams with complex constraints. Auton. Robots, 32(4):385–403, 2012.

T. Fawcett. Data mining with cellular automata. SIGKDD Explor. Newsl., 10(1):32–39, 2008.

F. A. Kolushev and A. A. Bogdanov. Multi-agent optimal path planning for mobile robots in environment with obstacles. In Ershov Memorial Conference, pages 503–510, 1999.

S. M. LaValle. Planning Algorithms. Cambridge University Press, 2006.



  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.