Efficient Boustrophedon multi-robot coverage: An algorithmic approach. (English) Zbl 1185.68744
Summary: This paper presents algorithmic solutions for the complete coverage path planning problem using a team of mobile robots. Multiple robots decrease the time to complete the coverage, but maximal efficiency is only achieved if the number of regions covered multiple times is minimized. A set of multi-robot coverage algorithms is presented that minimize repeat coverage. The algorithms use the same planar cell-based decomposition as the Boustrophedon single robot coverage algorithm, but provide extensions to handle how robots cover a single cell, and how robots are allocated among cells. Specifically, for the coverage task our choice of multi-robot policy strongly depends on the type of communication that exists between the robots. When the robots operate under the line-of-sight communication restriction, keeping them as a team helps to minimize repeat coverage. When communication between the robots is available without any restrictions, the robots are initially distributed through space, and each one is allocated a virtually-bounded area to cover. A greedy auction mechanism is used for task/cell allocation among the robots. Experimental results from different simulated and real environments that illustrate our approach for different communication conditions are presented.
Software:
COPL_DSDPReferences:
| [1] | Choset, H.: Coverage for robotics–a survey of recent results. Ann. Math. Artif. Intell. 31, 113–126 (2001) · Zbl 1314.68317 · doi:10.1023/A:1016639210559 |
| [2] | Latimer-IV, D., Srinivasa, S., Lee-Shue, V., Sonne, S.S., Choset, H., Hurst, A.: Toward sensor based coverage with robot teams. In: Proc. 2002 IEEE International Conference on Robotics & Automation (2002) |
| [3] | Rekleitis, I., Lee-Shue, V., New, A.P., Choset, H.: Limited communication, multi-robot team based coverage. In: IEEE International Conference on Robotics and Automation, pp. 3462–3468. New Orleasn, LA (2004) |
| [4] | Dias, M.B., Stentz, A.T.: A market approach to multirobot coordination. Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, Tech. Rep. CMU-RI -TR-01-26 (2001) |
| [5] | Choset, H., Pignon, P.: Coverage path planning: the Boustrophedon cellular decomposition. In: International Conference on Field and Service Robotics, Canberra, Australia (1997) |
| [6] | Canny, J.: Constructing roadmaps of semi-algebraic sets i : completeness. Artif. Intell. 37, 203–222 (1988) · Zbl 0668.14016 · doi:10.1016/0004-3702(88)90055-0 |
| [7] | Canny, J., Lin, M.: An opportunistic global path planner. Algorithmica 10, 102–120 (1993) · Zbl 0778.68095 · doi:10.1007/BF01891836 |
| [8] | Acar, E.U., Choset, H.: Critical point sensing in unknown environments. In: Proc. of the IEEE International Conference on Robotics & Automation (2000) |
| [9] | Oh, J.S., Park, J.B., Choi, Y.H.: Complete coverage navigation of clean robot based on triangularcell map. In: IEEE International Symposium on Industrial Electronics, vol. 3, pp. 2089–2093. Pusan, South Korea (2001) |
| [10] | Butler, Z.: CC R: a complete algorithm for contact-sensor based coverage of rectilinear environments. The Robotics Institute, Carnegie Mellon University, Tech. Rep. CMU-RI-TR-98-27 (1998) |
| [11] | Butler, Z., Rizzi, A., Hollis, R.: Distributed coverage of rectilinear environments. In: Proc. of the Workshop on the Algorithmic Foundations of Robotics (2001) · Zbl 0995.68126 |
| [12] | Kurabayashi, D., Ota, J., Arai, T., Yoshida, E.: An algorithm of dividing a work area to multiple mobile robots. In: 1995 IEEE/RSJ International Conference on Intelligent Robots and Systems, 5–9 Aug 1995, vol. 2, pp. 286–291 (1995) |
| [13] | Kurabayashi, D., Ota, J., Arai, T., Yoshida, E.: Cooperative sweeping by multiple mobile robots. In: 1996 IEEE International Conference on Robotics and Automation, 22–28 April 1996, vol. 2, pp. 1744–1749 (1996) |
| [14] | Min, T.W., Yin, H.K.: A decentralized approach for cooperative sweeping by multiple mobile robots. In: 1998 IEEE/RSJ International Conference on Intelligent Robots and Systems, 13–17 Oct. 1998, vol. 1, pp. 380–385 (1998) |
| [15] | Luo, C., Yang, S.: A real-time cooperative sweeping strategy for multiple cleaning robots. In: IEEE Internatinal Symposium on Intelligent Control, pp. 660–665 (2002) |
| [16] | Luo, C., Yang, S., Stacey, D.: Real-time path planning with deadlock avoidance of multiple cleaning robots. In: Proceedings 2003 IEEE International Conference on Robotics and Automation (ICRA), 14–19 Sept. 2003, vol. 3, pp. 4080–4085 (2003) |
| [17] | Ichikawa, S., Hara, F.: Characteristics of object-searching and object-fetching behaviors of multi-robot system using local communication. In: IEEE International Conference on Systems, Man, and Cybernetics, (IEEE SMC ’99), vol. 4, pp. 775–781 (1999) |
| [18] | Wagner, I., Lindenbaum, M., Bruckstein, A.: Distributed covering by ant-robots using evaporating traces. IEEE Trans. Robot. Autom. 15(5), 918–933 (1999) · doi:10.1109/70.795795 |
| [19] | Wagner, I.A., Lindenbaum, M., Bruckstein, A.M.: Mac vs. pc–determinism and randomness as complementary approaches to robotic exploration of continuous unknown domains. Int. J. Rob. Res. 19(1), 12–31 (2000) · doi:10.1177/02783640022066716 |
| [20] | Wagner, I.A., Altshuler, Y., Yanovski, V., Bruckstein, A.M.: Cooperative cleaners: a study in ant robotics. Int. J. Rob. Res. 27(1), 127–151 (2008) · doi:10.1177/0278364907085789 |
| [21] | Menezes, R., Martins, F., Vieira, F.E., Silva, R., Braga, M.: A model for terrain coverage inspired by ant’s alarm pheromones. In: Proceedings of the 2007 ACM symposium on Applied computing (SAC07), pp. 728–732. New York, NY, USA: ACM (2007) |
| [22] | Koenig, S., Szymanski, B.K., Liu, Y.: Efficient and inefficient ant coverage methods. Ann. Math. Artif. Intell. 31(1–4), 41–76 (2001). [Online]. Available: citeseer.ist.psu.edu/553035.html · doi:10.1023/A:1016665115585 |
| [23] | Ge, S.S., Fua, C.: Complete multi-robot coverage of unknown environments with minimum repeated coverage. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation (ICRA), 18–22 April 2005, pp. 715–720 (2005) |
| [24] | Bruemmer, D.J., Dudenhoeffer, D.D., Anderson, M.O., McKay, M.D.: A robotic swarm for spill finding and perimeter formation. International Conference on Nuclear and Hazardous Waste Management, Spectrum (2002) |
| [25] | Batalin, M.A., Sukhatme, G.S.: Spreading out: a local approach to multi-robot coverage. In: 6th International Symposium on Distributed Autonomous Robotics Systems, Fukuoka, Japan (2002), June |
| [26] | Spears, D., Kerr, W., Spears, W.: Physics-based robot swarms for coverage problems. Int. J. Intell. Control Syst. 11(3), 124–140 (2006) |
| [27] | Hazon, N., Kaminka, G.: Redundancy, efficiency and robustness in multi-robot coverage. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation (ICRA), 18–22 April 2005, pp. 735–741 (2005) |
| [28] | Hazon, N., Mieli, F., Kaminka, G.: Towards robust on-line multi-robot coverage. In: Proceedings 2006 IEEE International Conference on Robotics and Automation (ICRA), 15–19 May 2006, pp. 1710–1715 (2006) |
| [29] | Agmon, N., Hazon, N., Kaminka, G.: Constructing spanning trees for efficient multi-robot coverage. In: Proceedings 2006 IEEE International Conference on Robotics and Automation (ICRA), 15–19 May 2006, pp. 1698–1703 (2006) · Zbl 1185.68726 |
| [30] | Solanas, A., Garcia, M.: Coordinated multi-robot exploration through unsupervised clustering of unknown space. In: Proceedings 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems, vol. 1, 28 Sept–2 Oct. 2004, pp. 717–721 (2004) |
| [31] | Williams, K., Burdick, J.: Multi-robot boundary coverage with plan revision. In: Proceedings 2006 IEEE International Conference on Robotics and Automation (ICRA), 15–19 May 2006, pp. 1716–1723 (2006) |
| [32] | Zheng, X., Jain, S., Koenig, S., Kempe, D.: Multi-robot forest coverage. In: Proceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS), pp. 3852–3857. Edmonton Alberta, Canada (2005) |
| [33] | Dias, M.B., Zlot, R., Kalra, N., Stentz, A.: Market-based multirobot coordination: a survey and analysis. Robotics Institute, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, Tech. Rep. CMU-RI-TR-05-13 (2005) |
| [34] | Goldberg, D., Cicirello, V., Dias, M.B., Simmons, R., Smith, S.F., Stenz, A.: Market-based multi-robot planning in a distributed layered architecture. In: Multi-Robot Systems: From Swarms to Intelligent Automata: Proceedings from the 2003 International Workshop on Multi-Robot Systems, vol. 2, pp. 27–38. Kluwer Academic, Boston (2003) |
| [35] | Berhault, M., Huang, H., Keskinocak, P., Koenig, S., Elmaghraby, W., Griffin, P., Kleywegt, A.: Robot exploration with combinatorial auctions. In: IEEE/RSJ Int. Conference on Intelligent Robots and Systems, vol. 2, pp. 1957–1962 (2003) |
| [36] | Dias, M.B., Stentz, A.T.: Traderbots: a market-based approach for resource, role, and task allocation in multirobot coordination. Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, Tech. Rep. CMU-RI-TR-03-19 (2003) |
| [37] | Dias, M.B., Zinck, M., Zlot, R., Stentz, A.T.: Robust multirobot coordination in dynamic environments. In: International Conference on Robotics & Automation, pp. 3435–3442. New Orleans, LA (2004) |
| [38] | Gerkey, B., Mataric, M.: Sold!: auction methods for multirobot coordination. IEEE Trans. Robot. Autom. 18(5), 758–768 (2002) · doi:10.1109/TRA.2002.803462 |
| [39] | Zlot, R., Stentz, A.: Market-based multirobot coordination for complex tasks. International Journal of Robotics Research Special Issue on the 5th International Conference on Field and Service Robotics, vol. 25, no. 1, (2006) |
| [40] | Acar, E.U., Choset, H., Rizzi, A.A., Atkar, P.N., Hull, D.: Morse decompositions for coverage tasks. Int. J. Rob. Res. 21(4), 331–344 (2002) · doi:10.1177/027836402320556359 |
| [41] | Acar, E.U., Choset, H.: Sensor-based coverage of unknown environments: Incremental construction of morse decompositions. Int. J. Rob. Res. 21(4), 345–366 (2002) · doi:10.1177/027836402320556368 |
| [42] | Fomenko, A., Kunii, T.L.: Topological Modeling for Visualization. Tokio: Springer, New York (1997) · Zbl 1120.37300 |
| [43] | Rekleitis, I.M., Dudek, G., Milios, E.: Multi-robot collaboration for robust exploration. Ann. Math. Artif. Intell. 31(1–4), 7–40 (2001) · doi:10.1023/A:1016636024246 |
| [44] | Dellaert, F., Alegre, F., Martinson, E.B.: Intrinsic localization and mapping with 2 applications: diffusion mapping and marco polo localization. In: Proceedings of the 2003 IEEE International Conference on Robotics & Automation, Taipei, Taiwan, 14–19 September 2003, pp. 2344–2349 (2003) |
| [45] | Grabowski, R., P.Khosla, Choset, H.: Autonomous exploration via regions of interest. In: IEEE/RSJ Int. Conference on Intelligent Robots and Systems, vol. 1 (2003) |
| [46] | Vaughan, R.T.: Stage: a multiple robot simulator. Institute for Robotics and Intelligent Systems, School of Engineering, University of Southern California, Tech. Rep. IRIS-00-394 (2000) |
| [47] | Beineke, L.W., Wilson, R.J.: Selected Topics in Graph Theory 3. Academic, Boston (1988) |
| [48] | Hershberger, J., Suri, S.: An optimal algorithm for Euclidean shortest paths in the plane. SIAM J. Comput. 28(6), 2215–2256 (1999) · Zbl 0939.68157 · doi:10.1137/S0097539795289604 |
| [49] | Gerkey, B.P., Vaughan, R.T., Sty, K., Howard, A., Sukhatme, G.S., Mataric, M.J.: Most valuable player: a robot device server for distributed control. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2001), October 29–November 3 2001, pp. 1226–1231. Wailea, Hawaii (2001) |
| [50] | Schreckenghost, D., Bonasso, P., Kortenkamp, D., Ryan, D.: Three tier architecture for controlling space life support systems. In: IEEE Int. Joint Symposia on Intelligence and Systems, 21–23 May 1998, pp. 195–201 (1998) |
| [51] | Wagner, M., Apostolopoulos, D., Shillcutt, K., Shamah, B., Simmons, R., Whittaker, W.: The science autonomy system of the nomad robot. In: IEEE International Conference on Robotics and Automation, vol. 2, pp. 1742–1749 (2001) |
| [52] | Rtc, RTC, CMU, Pittsburgh, Pa (2000) |
| [53] | Raitner, M.: GTL–Graph Template Library Documentation, 1st edn. University of Passau–FMI–Theoretical Computer Science (2002) · Zbl 1037.68597 |
| [54] | Kong, C.S., New, A.P., Rekleitis, I.: Distributed coverage with multi-robot system. in Proc. of the IEEE International Conference on Robotics and Automation, pp. 2423–2429. Orlando, Florida (2006) |
| [55] | Rekleitis, I.M., New, A.P., Choset, H.: Distributed coverage of unknown/unstructured environments by mobile sensor networks. In: Schultz, A.C., Parker, L.E., Schneider, F. (eds.) 3rd International NRL Workshop on Multi-Robot Systems, 14–16 March 2005, pp. 145–155. Kluwer, Washington, D.C. (2005) |
| [56] | Roumeliotis, S.I., Rekleitis, I.M.: Propagation of uncertainty in cooperative multirobot localization: analysis and experimental results. Auton. Robots 17(1), 41–54 (2004) · doi:10.1023/B:AURO.0000032937.98087.91 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
