Open Access Open Access  Restricted Access Subscription Access

Dynamic Robot Path Planning With Cellular Automata

J. Santoso, O. Slamet Santoso, Riyanto Bambang

Abstract


In this paper we describe a novel approah the dynamic robot path planning with cellular automata. The idea is based on maximum clearence technique that keeps the distance of the robot to the obstacles as far as possible.  A similar work was implemented using a voronoi diagram to generate the candidate paths that  is safe from collision with  the obstacles. In fact, the maximum clearence method can be solved analitically using the deformation retraction,  but this approach is only applicable for the continuous environment and it requires a lot of  computing resources. Hence, we propose our approach to compute efficiently a robot path planning with cellular automata  that is suitable for the grid-based environtment.

Full Text:

PDF

References


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

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

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.

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.

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.

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.

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.

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.

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

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

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.

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. 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.

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.

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.

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




DOI: http://dx.doi.org/10.21535%2FProICIUS.2012.v8.791

Refbacks

  • There are currently no refbacks.