Abstract
We present an integrated approach to multirobot exploration, mapping and searching suitable for large teams of robots operating in unknown areas lacking an existing supporting communications infrastructure. We present a set of algorithms that have been both implemented and experimentally verified on teams—of what we refer to as Centibots—consisting of as many as 100 robots. The results that we present involve search tasks that can be divided into a mapping stage in which robots must jointly explore a large unknown area with the goal of generating a consistent map from the fragment, a search stage in which robots are deployed within the environment in order to systematically search for an object of interest, and a protection phase in which robots are distributed to track any intruders in the search area. During the first stage, the robots actively seek to verify their relative locations in order to ensure consistency when combining data into shared maps; they must also coordinate their exploration strategies so as to maximize the efficiency of exploration. In the second and third stages, robots allocate search tasks among themselves; since tasks are not defined a priori, the robots first produce a topological graph of the area of interest and then generate a set of tasks that reflect spatial and communication constraints. Our system was evaluated under extremely realistic real-world conditions. An outside evaluation team found the system to be highly efficient and robust.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Arkin, R.C.: Behavior-based Robotics. MIT, Cambridge (1998)
Barraquand, J., Langlois, B., Latombe, J.C.: Robot motion planning with many degrees of freedom and dynamic constraints. In: Miura, H., Arimoto, S. (eds.) Robotics Research, vol. 5, pp. 435–444. MIT, Cambridge (1990)
Burgard, W., Moors, M., Fox, D., Simmons, R., Thrun, S.: Collaborative multi-robot exploration. In: Proc. of the IEEE International Conference on Robotics & Automation (ICRA) (2000)
Burgard, W., Moors, M., Stachniss, C., Schneider, F.: Coordinated multi-robot exploration. IEEE Trans. Robot. 21, 376–386 (2005)
Dedeoglu, G., Sukhatme, G.S.: Landmark-based matching algorithm for cooperative mapping by autonomous robots. In: Proc. of the 5th International Symposium on Distributed Autonomous Robotic Systems (DARS) (2000)
Dissanayake, M.W.M., Newman, P., Clark, S., Durrant-Whyte, H.F., Csorba, M.: A solution to the simultaneous localization and map building (SLAM) problem. IEEE Trans. Robot. Autom. 17(3), 229–241 (2001)
Keith Edwards, W.: Core Jini. Prentice Hall, Englewood Cliffs (2001)
Eliazar, A., Parr, R.: DP-SLAM: fast, robust simultaneous localization and mapping without predetermined landmarks. In: Proc. of the International Joint Conference on Artificial Intelligence (IJCAI) (2003)
Fenwick, J.W., Newman, P.M., Leonard, J.J.: Cooperative concurrent mapping and localization. In: Proc. of the IEEE International Conference on Robotics & Automation (ICRA) (2002)
Fox, D.: Adapting the sample size in particle filters through KLD-sampling. Int. J. Robot. Res. (IJRR) 22(12) (2003)
Fox, D., Burgard, W., Dellaert, F., Thrun, S.: Monte Carlo localization: efficient position estimation for mobile robots. In: Proc. of the National Conference on Artificial Intelligence (AAAI) (1999)
Fox, D., Ko, J., Konolige, K., Limketkai, B., Stewart, B.: Distributed multi-robot exploration and mapping. In: Proc. of the IEEE. Special Issue on Multi-Robot Systems (2006)
Fox, D., Ko, J., Konolige, K., Limketkai, B., Stewart, B.: Distributed multi-robot exploration and mapping. In: Proc. of the IEEE, vol. 94(7). Special Issue on Multirobot Systems (2006)
Fox, D., Ko, J., Konolige, K., Stewart, B.: A hierarchical Bayesian approach to mobile robot map structure learning. In: Dario, P., Chatila, R. (eds.) Robotics Research: the Eleventh International Symposium. Springer Tracts in Advanced Robotics (STAR). Springer, New York (2005)
Gerkey, B., Mataric, M.: Multi-robot task allocation: Analyzing the complexity and optimality of key architectures. In: Proc. of the IEEE International Conference on Robotics & Automation (ICRA) (2003)
Grosz, B.J., Kraus, S.: Collaborative plans for complex group action. Artif. Intell. 86(1), 269–357 (1996)
Gutmann, J.S., Konolige, K.: Incremental mapping of large cyclic environments. In: Proc. of the IEEE International Symposium on Computational Intelligence in Robotics and Automation (CIRA) (1999)
Hähnel, D., Burgard, W., Fox, D., Thrun, S.: An efficient FastSLAM algorithm for generating maps of large-scale cyclic environments from raw laser range measurements. In: Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (2003)
Howard, A., Parker, L.E., Sukhatme, G.S.: The SDR experience: experiments with a large-scale heterogenous mobile robot team. In: Proc. of the International Symposium on Experimental Robotics (ISER) (2004)
Jensfelt, P., Wijk, O., Austin, D., Andersson, M.: Feature based condensation for mobile robot localization. In: Proc. of the IEEE International Conference on Robotics & Automation (ICRA) (2000)
Ko, J., Stewart, B., Fox, D., Konolige, K., Limketkai, B.: A practical, decision-theoretic approach to multi-robot mapping and exploration. In: Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (2003)
Koenig, S., Tovey, C., Halliburton, W.: Greedy mapping of terrain. In: Proc. of the IEEE International Conference on Robotics & Automation (ICRA) (2001)
Konolige, K.: Large-scale map making. In: Proc. of the National Conference on Artificial Intelligence (AAAI) (2004)
Konolige, K.: SLAM via variable reduction from constraint maps. In: Proc. of the IEEE International Conference on Robotics & Automation (ICRA) (2005)
Konolige, K., Fox, D., Ortiz, C., Agno, A., Eriksen, M., Limketkai, B., Ko, J., Morisset, B., Schulz, D., Stewart, B., Vincent, R.: Centibots: very large scale distributed robotic teams. In: Ang, M., Khatib, O. (eds.) Experimental Robotics: the 9th International Symposium, Springer Tracts in Advanced Robotics (STAR). Springer, New York (2005)
Konolige, K.: A gradient method for realtime robot control. In: Proceedings of IROS (2000)
Konolige, K., Myers, K., Ruspini, E., Saffiotti, A.: The saphira architecture: a design for autonomy. J. Exp. Theor. Artif. Intell. 9 (1996)
Lenser, S., Veloso, M.: Sensor resetting localization for poorly modelled mobile robots. In: Proc. of the IEEE International Conference on Robotics & Automation (ICRA) (2000)
Lu, F., Milios, E.: Globally consistent range scan alignment for environment mapping. Auton. Robots 4, 333–349 (1997)
Montemerlo, M., Thrun, S., Koller, D., Wegbreit, B.: FastSLAM: a factored solution to the simultaneous localization and mapping problem. In: Proc. of the National Conference on Artificial Intelligence (AAAI) (2002)
Moorehead, S.: Autonomous Surface Exploration for Mobile Robots. PhD Thesis, Carnegie Mellon University (2001)
Murphy, K.: Bayesian map learning in dynamic environments. In: Advances in Neural Information Processing Systems (NIPS) (1999)
Nettleton, E., Thrun, S., Durrant-Whyte, H.: Decentralised SLAM with low-bandwith communications for teams of airborne vehicles. In: Proc. of the International Conference on Field and Service Robotics (2003)
Newman, P., Leonard, J.J.: Consistent convergent constant time SLAM. In: Proc. of the International Joint Conference on Artificial Intelligence (IJCAI) (2003)
Ogier, R.G., Templin, F.L., Lewis, M.G.: Topology dissemination based on reverse-path forwarding. IETF RFC 3684 (Experimental) (2004)
Paskin, M.A.: Thin junction tree filters for simultaneous localization and mapping. In: Proc. of the International Joint Conference on Artificial Intelligence (IJCAI) (2003)
Pynadath, D.V., Tambe, M.: Automated teamwork among heterogeneous software agents and humans. J. Auton. Agents Multi-Agent Syst. 7, 71–100 (2003)
Saffiotti, A., Ruspini, E.H., Konolige, K.: Integrating reactivity and goal-directedness in a fuzzy controller. In: Proceedings of the 2nd Fuzzy-IEEE Conference (1993)
Simmons, R., Apfelbaum, D., Burgard, W., Fox, D., Moors, M., Thrun, S., Younes, H.: Coordination for multi-robot exploration and mapping. In: Proc. of the National Conference on Artificial Intelligence (AAAI) (2000)
Stewart, B., Ko, J., Fox, D., Konolige, K.: The revisiting problem in mobile robot map building: a hierarchical Bayesian approach. In: Proc. of the Conference on Uncertainty in Artificial Intelligence (UAI) (2003)
Stroupe, A., Ravichandran, R., Balch, T.: Value-based action selection for exploration and dynamic target observation with robot teams. In: Proc. of the IEEE International Conference on Robotics & Automation (ICRA) (2004)
Thrun, S.: A probabilistic online mapping algorithm for teams of mobile robots. Int. J. Robot. Res. 20(5) (2001)
Thrun, S.: Robotic mapping: a survey. In: Lakemeyer, G., Nebel, B. (eds.) Exploring Artificial Intelligence in the New Millenium. Morgan Kaufmann, San Francisco (2002)
Thrun, S., Burgard, W., Fox, D.: Probabilistic Robotics. MIT, Cambridge (2005)
Wilkins, D.E., Lee, T., Berry, P.: Interactive execution monitoring of agent teams. J. Artif. Intell. Res. 18, 217–261 (2003)
Williams, S.B., Dissanayake, G., Durrant-Whyte, H.: Towards multi-vehicle simultaneous localisation and mapping. In: Proc. of the IEEE International Conference on Robotics & Automation (ICRA) (2002)
Yamauchi, B.: Frontier-based exploration using multiple robots. In: Proc. of the Second International Conference on Autonomous Agents (1998)
Zlot, R., Stentz, A., Bernardine Dias, M., Thayer, S.: Multi-robot exploration controlled by a market economy. In: Proc. of the IEEE International Conference on Robotics & Automation (ICRA) (2002)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Vincent, R., Fox, D., Ko, J. et al. Distributed multirobot exploration, mapping, and task allocation. Ann Math Artif Intell 52, 229–255 (2008). https://doi.org/10.1007/s10472-009-9124-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-009-9124-y