Greedy Algorithm Based Multiple Target Searching for Mobile Robots

Abstract:

The article mainly researches path planning and task allocation problems of multiple mobile robots using A* searching algorithm and greedy algorithm, and solve the shortest path problems such that the robots can move from the start point to reach the multiple target points in a collision-free space, and uses 2-opt exchange heuristic algorithm to improve the shortest path. In this manner, the mobile moves to the final target point through the other points, and construct the motion path using A* searching algorithm and greedy algorithm. The supervised computer control the mobile robot feedback to the start point from the final target point through the other points, and programs a shortest path using 2-opt exchange heuristic algorithm. We develop the user interface to program the motion path of mobile robots via wireless RF interface. It can displays the motion path of the mobile robot on real-time. The simulated results presents that the proposed method can finds the shortest motion path for mobile robots moving to multiple target points from the start point in a collision-free space. Finally, we implement the experiment scenario on the grid platform using the module-based mobile robot.

• Periodical: Applied Mechanics and Materials (Volumes 44-47)
• Pages: 1335-1339
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.44-47.1335
• Online since: December 2010
• Authors: J. Hung Guo, Kuo Lan Su
• Keywords: 2-Opt Exchange Heuristic Algorithm, Greedy Algorithm, Multiple Mobile Robot, Path Planning, Searching Algorithm

References

[1] G. Antonelli, S. Chiaverini and G. Fusco: A fuzzy-logic-based approach for mobile robot path tracking, The IEEE Trasaction on Fuzzy System , Vol. 15, No. 2, pp.211-221, (2007).

DOI: 10.1109/tfuzz.2006.879998

[2] P. Rusu, E. M. Petriu, T. E. Whalen, A. Cornell and H. J. W. Spoelder: Behavior-based neuron-fuzzy controller for mobile robot navigation, IEEE Trans. Instrum. Meas., Vol. 52, No. 4, pp.1335-1340, (2003).

DOI: 10.1109/tim.2003.816846

[3] A. Chatterjee, K. Pulasinghe, K. Watanabe and K. Izumi: A pratical swarm-optimized fuzzy-neural network for voice-controlled robot systems, IEEE Trans. Ind. Electron., Vol. 52, No. 6, pp.1478-1489, (2005).

DOI: 10.1109/tie.2005.858737

[4] M. J. Er and C. Deng: Online tuning of fuzzy inference system using dynamic fuzzy Q-learning, IEEE Trans. Syst. Man. Cybern. B, Cybern., Vol. 34, No. 3, pp.1478-1489, (2004).

DOI: 10.1109/tsmcb.2004.825938

[5] A. K. Kulatunga, D. k. Liu and G. Dissanayake: Ant colony optimization based simultaneous task allocation and path planning of autonomous vehicles, IEEE Conference on Cybernetics and Intelligent System, pp.1-6, (2006).

DOI: 10.1109/iccis.2006.252349

[6] S Liu, L. Mao and J. Yu: Path planning based on ant colony algorithm and distributed local navigation for multi-robot systems, IEEE International Conference on Mechatronics and Automation, pp.1733-1738, (2006).

DOI: 10.1109/icma.2006.257476

[7] C. F. Juang and C. H. Hsu: Reinforcement ant optimized fuzzy controller for mobile-robot wall-following control, IEEE Transactions on Industrial Electronics, Vol. 56, No. 10, pp.3931-3940, (2009).

DOI: 10.1109/tie.2009.2017557

[8] K. Sugihara and J. Smith: Genetic algorithm for adaptive motion planning of an autonomous mobile robot, IEEE International Symposium on Computational Intelligence in Robotics and Automation, Monterey, CA; pp.138-146, (1997).

DOI: 10.1109/cira.1997.613850

[9] X. F. Dai, X. M. Ning and Y. Shi: A novel path planning algorithm for mobile robots based on cloud model, ICIC Express Letters, Vol. 3, N0. 4(A), pp.877-882, (2009).

[10] J. Zhou, G. Z. Dai, D. Q. He, J. Ma and X. Y. Cai: Swarm intelligent: ant-based robot path planning, IEEE International Conference on Information Assurance and Security, pp.459-463, (2006).

DOI: 10.1109/ias.2009.120

[11] T. G. Zheng and H. E. Huan: Ant colony system algorithm for real-time globally optimal path planning of mobile robots, Acta Automatica Sinica, Vol. 33, Issue 3, pp.279-285, March (2007).

DOI: 10.1360/aas-007-0279

[12] A. Y. Saber and T. Senjyu: Memory-bounded ant colony optimization with dynamic programming and A* local search for generator planning, IEEE Trans. on Power System, Vol. 22, No. 4, pp.1965-1973, (2007).

DOI: 10.1109/tpwrs.2007.907382

[13] S. Miyata, A. Yanou, H. Nakamura and S. Takehara: Automatic path search for roving robot using reinforcement learning, ICIC Express-Letters, Vol. 4, No. 3(B), pp.885-892, (2010).

DOI: 10.1109/icicic.2009.121

[14] V. Mizumoto, J. Yu and K. Shibayama: 3D path planning for mobile robots using simulated annealing neural network, International Journal of Innovative Computing, Information and Control, Vol. 6, No. 7, pp.2885-2900, (2010).

[15] W. Yuan and B. Zeng: Multi-robot task allocation using abandoned-undertaking algorithm, The Fourth International Conference on Natural Computation, pp.404-408, (2008).

DOI: 10.1109/icnc.2008.42

[16] L. E. Parker: An architecture for fault tolerant multi-robot cooperation, IEEE Transaction on Robotics and Automation, Vol. 14, No. 2, pp.220-240, (1998).

DOI: 10.1109/70.681242

[17] B. P. Gerkey and M. J. Mataric: Auction method for multi-robot coordination, IEEE Transaction on Robotics and Automation, Vol. 18, No. 5, pp.758-768, (2002).

DOI: 10.1109/tra.2002.803462

[18] B. P. Gerkey, On multi-robot task allocation, PhD thesis, University of Southern California, August, (2003).

[19] S. V. Shiau, K. L. Su, C. C. Wang and J. H. Guo: Formation exchange of the multiple mobile robot system, " International Symposium on Computer, Communication, Control and Automation, May 5-7, 2010, No. 2, pp.265-269.

DOI: 10.1109/3ca.2010.5533529