Dynamic Path Planning for Mobile Robots with Cellular Learning Automata
DOI:
https://doi.org/10.5614/itbj.ict.res.appl.2016.10.1.1Abstract
In this paper we propose a new approach to path planning for mobile robots with cellular automata and cellular learning automata. We divide the planning into two stages. In the first stage, global path planning is performed by cellular automata from an initial position to a goal position. In this stage, the minimum distance is computed. To compute the path, we use a particular two-dimensional cellular automata rule. The process of computation is performed using simple arithmetic operations, hence it can be done efficiently. In the second stage, local planning is used to update the global path. This stage is required to adapt to changes in a dynamic environment. This planning is implemented using cellular learning automata to optimize performance by collecting information from the environment. This approach yields a path that stays near to the obstacles and therefore the total time and distance to the goal can be optimized.Downloads
References
Desaraju, V. & How, J.P., Decentralized Path Planning for Multi-Agent Teams with Complex Constraints, Auton. Robots, 32(4), pp. 385-403, 2012.
Kolushev, F.A. & Bogdanov, A.A., Multi-Agent Optimal Path Planning for Mobile Robots in Environment with Obstacles, Ershov Memorial Conference, pp. 503-510, 1999.
Thrun, S., Robotic Mapping: A Survey, in Exploring Artificial Intelligence in the New Millenium, Lakemeyer, G. & Nebel, B., eds., Morgan Kaufmann, San Fransisco, USA, 2002.
Androulakis, I.P., Dynamic Programming: Stochastic Shortest Path Problems, Encyclopedia of Optimization, pp. 869-873, 2009.
Moungla, N.T., Letocart, L. & Nagih, A., An Improving Dynamic Programming Algorithm to Solve the Shortest Path Problem with Time Windows, Electronic Notes in Discrete Mathematics, 36, pp. 931-938, 2010.
Ioannidis, K., Sirakoulis, G.C. & Andreadis, I., A Path Planning Method Based on Cellular Automata for Cooperative Robots, Applied Artificial Intelligence, 25(8), pp. 721-745, 2011.
Marchese, F. M., A Path-Planner for Mobile Robots of Generic Shape with Multilayered Cellular Automata, Proceedings of 5th International Conference on Cellular Automata for Research and Industry, ACRI, Geneva, Switzerland, pp. 178-189, 2002.
Santoso, J., Trilaksono, B.R., Santoso, O.S. & Adiprawita, W., Path Planning for Multi Robot with Cellular Automata, 2013 International Conference on Robotics, Biomimetics, Intelligent Computational Systems (ROBIONETICS), pp. 19-23, 2013.
Santoso, J., Trilaksono, B.R., & Santoso, O.S., Path Planning for Mobile Robot with Cellular Automata, Journal Unmanned System Technology, 1(2), PP.43-48, 2013.
Bagnoli, F., Cellular Automata, in Dynamical Modelling in Biotechnologies, Bagnoli, F., Lio', P. & Ruffo, S., eds., World Scientific, Singapore, 1998.
Wolfram, S., A New Kind of Science, Wolfram-Media, Inc., Champaign, Illinois, United States, p. 170, 2002.
Mitchell, M., Computation in Cellular Automata: A Selected Review, in Nonstandard Computation, Gramss, T., Bornholdt, S., Gross, M., Mitchell, M. & Pellizzari, T., Weinheim: VCH Verlagsgesellschaft., pp. 95-140, 1996.
Santoso, J., Santoso, O.S., & Trilaksono, B.R., Matrix Characteristics for Two Dimensional Nongroup Cellular Automata, Proceedings of the 2011 International Conference on Electrical Engineering and Informatics, STEI-ITB, Bandung, pp. 2-4, 2011.
Navid, A.H.F. & Aghababa, A.B.., Cellular Learning Automata and Its Applications, in Emerging Applications of Cellular Automata, Salcido, A., eds., pp.85-111, 2013.
Abdolzadeh, M. & Rashidi, H., Solving Job Shop Scheduling Problem Using Cellular Learning Automata, Computer Modeling and Simulation, EMS '09. Third UKSim European Symposium, pp. 49-54, 2009.
Beigy, H. & Meybodi, M.R., Cellular Learning Automata with Multiple Learning Automata in Each Cell and Its Applications, Trans. Sys. Man Cyber. Part B, 40(1), pp. 54-65, Feb. 2010.
Quigley, M., Conley, K., Gerkey, B.P., Faust, J., Foote, T., Leibs, J., Wheeler, R. & Andrew, Y. Ng., ROS: An Open-source Robot Operating System, in ICRA Workshop on Open Source Software, 2009.
Koenig, N. & Howard, A., Design and Use Paradigms for Gazebo, An Open-Source Multi-Robot Simulator, In IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2149-2154, 2004.
