Influence of Field Structure on the Multi-Agent Coverage Algorithm on Unknown Fields

Hidemi Yamachi; Yasuhiro Tsujimura; Yasushi Kambayashi

doi:10.20965/jaciii.2013.p0883

single-jc.php

« previous

JACIII Vol.17 No.6 pp. 883-889

doi: 10.20965/jaciii.2013.p0883

(2013)

Paper:

Views over last 60 days: 964

Influence of Field Structure on the Multi-Agent Coverage Algorithm on Unknown Fields

Hidemi Yamachi, Yasuhiro Tsujimura, and Yasushi Kambayashi

Department of Computer and Information Engineering, Nippon Institute of Technology, 4-1 Gakuendai Miyashiro, Saitama 345-0826, Japan

Received:

May 16, 2013

Accepted:

September 26, 2013

Published:

November 20, 2013

Keywords:

multi-agent, coverage, unknown field, shortest path

Abstract

There are a lot of researches and applications for the coverage problem of unknown fields by a robot, for example, planet exploration, mine-clearing operation. Using multi-robots for this problem we can expect effective operation. In order to control multi-robots effectively, obtaining cooperative action among robots is essential. We have proposed an algorithm for the cooperative multi-agent coverage simulation. There are three possible coverage paths: the zigzag, spiral and random paths. We have compared the effectiveness of those three coverage paths for a field where complex obstacles are allocated. The experimental results show that there are no remarkable differences of effectiveness among those three coverage paths. It is still not clear that how the shape or the allocation of obstacles affect the effectiveness of the coverage paths. In this paper we evaluate the influence of the field structure on the effectiveness of the coverage paths.

Cite this article as:

H. Yamachi, Y. Tsujimura, and Y. Kambayashi, “Influence of Field Structure on the Multi-Agent Coverage Algorithm on Unknown Fields,” J. Adv. Comput. Intell. Intell. Inform., Vol.17 No.6, pp. 883-889, 2013.

Data files:

References

[1] M. Takimoto, M. Mizuno, M. Kurio, and Y. Kambayashi, “Saving Energy Consumption of Multi-Robots Using Higher-Order Mobile Agents,” First KES Int. Symp. on Agent and Multi-Agent Systems: Technologies and Applications, LNCS 4496, Springer-Verlag, pp. 549-558, 2007.
[2] P. Stone and M. Veloso, “Multiagent systems: A survey from a machine learning perspective,” Autonomous Robots, Vol.8, No.3, pp. 345-383, 2000.
[3] T. Yasuda and K. Ohkura, “Autonomous role assignment in a homogeneous multi-robot systems,” J. of Robotics and Mechatronics, Vol.17, No.5, pp. 596-604, 2005.
[4] E. Gerlein and E. Gonzalez, “Multirobot cooperative model applied to coverage of unknown regions,” Multi-Robot Systems, Trends and Development, InTech, pp. 109-130, 2011.
[5] Y. Gabriely and E. Rimon, “Spanning-tree based coverage of continuous areas by a mobile robot,” Annals of Mathematics and Artificial Intelligence, Vol.31, No.1-4, pp. 77-98, 2001.
[6] N. Hazon and G. A. Kaminka, “Redundancy, efficiency and robustness in multi-robot coverage,” Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), pp. 735-741, 2005.
[7] N. Agmon, N. Hazon, and G. A. Kaminka, “The giving tree: constructing trees for efficient offline and online multi-robot coverage,” Annals of Mathematics and Artificial Intelligence, Vol.52, pp. 143-168, 2008.
[8] H. Choset et al., “Principles of robot motion theory, algorithms, and implementation,” MIT Press, 2004.
[9] E. Gonzalez et al., “BSA: A complete coverage algorithm,” Proc. of the 2005 IEEE Int. Conf. on Robotics and Automation, pp. 2040-2044, 2005.
[10] E. Gerlein and E.Gonzalez, “BSA-CM: A multi-robot coverage algorithm,” IEEE/WIC/ACMInt. Conf. on Intelligent Agent Technology, pp. 383-386, 2009.
[11] S. S. Ge and C. Fua, “Complete Multi-Robot Coverage of Unknown Environments with Minimum Repeated Coverage,” Proc. of the 2005 IEEE Int. Conf. on Robotics and Automation, pp. 715-720, 2005.
[12] H. Yamachi, Y. Tsujimura, Y. Kambayashi, and T. Iida, “Evaluation of multi-agent simulation for coverage algorithm on unknown field,” Proc. of the 16th Asia Pacific Symp. on Intelligent and Evolutionary Systems, pp. 141-146, 2012.

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[1] [1] M. Takimoto, M. Mizuno, M. Kurio, and Y. Kambayashi, “Saving Energy Consumption of Multi-Robots Using Higher-Order Mobile Agents,” First KES Int. Symp. on Agent and Multi-Agent Systems: Technologies and Applications, LNCS 4496, Springer-Verlag, pp. 549-558, 2007.

[2] [2] P. Stone and M. Veloso, “Multiagent systems: A survey from a machine learning perspective,” Autonomous Robots, Vol.8, No.3, pp. 345-383, 2000.

[3] [3] T. Yasuda and K. Ohkura, “Autonomous role assignment in a homogeneous multi-robot systems,” J. of Robotics and Mechatronics, Vol.17, No.5, pp. 596-604, 2005.

[4] [4] E. Gerlein and E. Gonzalez, “Multirobot cooperative model applied to coverage of unknown regions,” Multi-Robot Systems, Trends and Development, InTech, pp. 109-130, 2011.

[5] [5] Y. Gabriely and E. Rimon, “Spanning-tree based coverage of continuous areas by a mobile robot,” Annals of Mathematics and Artificial Intelligence, Vol.31, No.1-4, pp. 77-98, 2001.

[6] [6] N. Hazon and G. A. Kaminka, “Redundancy, efficiency and robustness in multi-robot coverage,” Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), pp. 735-741, 2005.

[7] [7] N. Agmon, N. Hazon, and G. A. Kaminka, “The giving tree: constructing trees for efficient offline and online multi-robot coverage,” Annals of Mathematics and Artificial Intelligence, Vol.52, pp. 143-168, 2008.

[8] [8] H. Choset et al., “Principles of robot motion theory, algorithms, and implementation,” MIT Press, 2004.

[9] [9] E. Gonzalez et al., “BSA: A complete coverage algorithm,” Proc. of the 2005 IEEE Int. Conf. on Robotics and Automation, pp. 2040-2044, 2005.

[10] [10] E. Gerlein and E.Gonzalez, “BSA-CM: A multi-robot coverage algorithm,” IEEE/WIC/ACMInt. Conf. on Intelligent Agent Technology, pp. 383-386, 2009.

[11] [11] S. S. Ge and C. Fua, “Complete Multi-Robot Coverage of Unknown Environments with Minimum Repeated Coverage,” Proc. of the 2005 IEEE Int. Conf. on Robotics and Automation, pp. 715-720, 2005.

[12] [12] H. Yamachi, Y. Tsujimura, Y. Kambayashi, and T. Iida, “Evaluation of multi-agent simulation for coverage algorithm on unknown field,” Proc. of the 16th Asia Pacific Symp. on Intelligent and Evolutionary Systems, pp. 141-146, 2012.