Abstract
Whenever multiple robots have to solve a common task, they need to coordinate their actions to carry out the task efficiently and to avoid interferences between individual robots. This is especially the case when considering the problem of exploring an unknown environment with a team of mobile robots. To achieve efficient terrain coverage with the sensors of the robots, one first needs to identify unknown areas in the environment. Second, one has to assign target locations to the individual robots so that they gather new and relevant information about the environment with their sensors. This assignment should lead to a distribution of the robots over the environment in a way that they avoid redundant work and do not interfere with each other by, for example, blocking their paths. In this paper, we address the problem of efficiently coordinating a large team of mobile robots. To better distribute the robots over the environment and to avoid redundant work, we take into account the type of place a potential target is located in (e.g., a corridor or a room). This knowledge allows us to improve the distribution of robots over the environment compared to approaches lacking this capability. To autonomously determine the type of a place, we apply a classifier learned using the AdaBoost algorithm. The resulting classifier takes laser range data as input and is able to classify the current location with high accuracy. We additionally use a hidden Markov model to consider the spatial dependencies between nearby locations. Our approach to incorporate the information about the type of places in the assignment process has been implemented and tested in different environments. The experiments illustrate that our system effectively distributes the robots over the environment and allows them to accomplish their mission faster compared to approaches that ignore the place labels.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Albers, S., Kursawe, K., Schuierer, S.: Exloring unknown environments with obstacles. Algotithmica, 32, 123–143 (2002)
Althaus, P., Christensen, H.I.: Behaviour coordination in structured environments. Adv. Robot. 17(7), 657–674 (2003)
Bender, M., Slonim, D.: The power of team exploration: two robots can learn unlabeled directed graphs. In: Proc. of the 35th Annual Symposium on Foundations of Computer Science, pp. 75–85, Santa Fe, 20–22 November 1994
Burgard, W., Moors, M., Stachniss, C., Schneider, F.: Coordinated multi-robot exploration. IEEE Trans. Robot. 21(3), 376–378 (2005)
Cao, Y.U., Fukunaga, A.S., Khang, A.B.: Cooperative mobile robotics: antecedents and directions. J. Auton. Robots 4(1), 7–27 (1997)
Choset, H.: Topological simultaneous localization and mapping (SLAM): toward exact localization without explicit localization. IEEE Trans. Robot. Autom. 17(2), 125–137 (2001)
Deng, X., Kameda, T., Papadimitriou, C.: How to learn in an unknown environment. In: Proc. of the 32nd Symposium on the Foundations of Computational Science, pp. 298–303. IEEE Computer Society Press, Los Alamitos (1991)
Deng, X., Papadimitriou, C.: How to learn in an unknown environment: the rectilinear case. J. ACM 45(2), 215–245 (1998)
Dudek, G., Jenkin, M., Milios, E., Wilkes, D.: Robotic exploration as graph construction. IEEE Trans. Robot. Autom. 7(6), 859–865 (1991)
Dudek, G., Jenkin, M., Milios, E., Wilkes, D.: A taxonomy for multi-agent robotics. J. Auton. Robots 3(4), 375–397 (1996)
Edlinger, T., von Puttkamer, E.: Exploration of an indoor-environment by an autonomous mobile robot. In: Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pp. 1278–1248, Munich, 12–16 September 1994
Fox, D., Burgard, W., Kruppa, H., Thrun, S.: Collaborative multi-robot localization. In: Proc. of the 23rd German Conference on Artificial Intelligence, pp. 325–340. Springer, New York (1999)
Fox, D., Ko, J., Konolige, K., Stewart, B.: A hierarchical bayesian approach to the revisiting problem in mobile robot map building. In: Proc. of the Int. Symposium of Robotics Research (ISRR), Siena, 19–22 October 2003
Freund, Y., Schapire, R.E.: A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci. 55(1), 119–139 (1997)
Gerkey, B.P., Matarić, M.J.: Sold!: auction methods for multirobot coordination. IEEE Trans. Robot. Autom. 18(5), 758–768 (2002)
Goldberg, D., Matarić, M.J.: Interference as a tool for designing and evaluating multi-robot controllers. J. Robot. Auton. Syst. 8, 637–642 (1997)
Gonzalez, R.C., Wintz, P.: Digital Image Processing. Addison-Wesley, Reading (1987)
González-Baños, H.H., Mao, E., Latombe, J.C., Murali, T.M., Efrat, A.: Planning robot motion strategies for efficient model construction. In: Proc. Int. Symp. on Robotics Research (ISRR), pp. 345–352, Snowbird, 2000
Guzzoni, D., Cheyer, A., Julia, L., Konolige, K.: Many robots make short work. AI Mag. 18(1), 55–64 (1997)
Howard, A.: Multi-robot simultaneous localization and mapping using particle filters. In: Robotics: Science and Systems, pp. 201–208, Cambridge, 2005
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 Int. Conf. on Intelligent Robots and Systems (IROS), pp. 3232–3238, Las Vegas, 2003
Koenig, S., Simmons, R.: Xavier: a robot navigation architecture based on partially observable markov decision process models. In: Kortenkamp, D., Bonasso, R., Murphy, R. (eds.) Artificial Intelligence Based Mobile Robotics: Case Studies of Successful Robot Systems, pp. 91–122. MIT, Cambridge (1998)
Koenig, S., Szymanski, B., Liu, Y.: Efficient and inefficient ant coverage methods. Ann. Math. Artif. Intell. 31, 41–76 (2001)
Koenig, S., Tovey, C., Halliburton, W.: Greedy mapping of terrain. In: Proc. of the IEEE Int. Conf. on Robotics & Automation (ICRA), Seoul, 2001
Kuipers, B., Beeson, P.: Bootstrap learning for place recognition. In: Proc. of the National Conference on Artificial Intelligence (AAAI), Edmonton, 2002
Kuipers, B., Byun, Y.-T.: A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations. J. Robot. Auton. Syst. 8, 47–63 (1991)
Kurazume, R., Shigemi, N.: Cooperative positioning with multiple robots. In: Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pp. 1250–1257, Munich, 1994
Lee, D., Recce, M.: Quantitative evaluation of the exploration strategies of a mobile robot. Int. J. Rob. Res. 16(4), 413–447 (1997)
Martínez-Mozos, O., Stachniss, C., Burgard, W.: Supervised learning of places from range data using adaboost. In: Proc. of the IEEE Int. Conf. on Robotics & Automation (ICRA), pp. 1742–1747, Barcelona, 2005
Matarić, M.J., Sukhatme, G.: Task-allocation and coordination of multiple robots for planetary exploration. In: Proc. of the Int. Conf. on Advanced Robotics (ICAR), pp. 61–70, Budapest, 2001
Meijster, A., Roerdink, J.B.T.M., Hesselink, W.H.: Mathematical Morphology and its Applications to Image and Signal Processing, Chapter A. General Algorithm for Computing Distance Transforms in Linear Time, pp. 331–340. Kluwer, Dordrecht (2000)
Oore, S., Hinton, G.E., Dudek, G.: A mobile robot that learns its place. Neural Comput. 9(3), 683–699 (1997)
Rekleitis, I., Dudek, G., Milios, E.: Multi-robot exploration of an unknown environment, efficiently reducing the odometry error. In: Proc. of International Joint Conference in Artificial Intelligence (IJCAI), vol. 2, pp. 1340–1345 (1997)
Rekleitis, I., Lee-Shue, V., Peng New, A., Choset, H.: Limited communication, multi-robot team based coverage. In: Proc. of the IEEE Int. Conf. on Robotics & Automation (ICRA), pp. 3462–3468, New Orleans, 2004
Rekleitis, I., Sim, R., Dudek, G., Milios, E.: Collaborative exploration for the construction of visual maps. In: Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), Maui, 2001
Roy, N., Dudek, G.: Collaborative robot exploration and rendezvous: algorithms, performance bounds and observations. J. Auton. Robots 11(2), 117–136 (2001)
Sack, D., Burgard, W.: A comparison of methods for line extraction from range data. In: Proc. of the IFAC Symposium on Intelligent Autonomous Vehicles (IAV), Lisbon, 2004
Schneider-Fontan, M., Matarić, M.J.: Territorial multi-robot task division. IEEE Trans. Robot. Autom. 14(5), 815–822 (1998)
Stachniss, C.: Exploration and Mapping with Mobile Robots. PhD thesis, University of Freiburg, Department of Computer Science (2006)
Stachniss, C., Martínez-Mozos, O., Burgard, W.: Speeding-up multi-robot exploration by considering semantic place information. In: Proc. of the IEEE Int. Conf. on Robotics & Automation (ICRA), pp. 1692–1697, Orlando, 2006
Stroupe, A.W., Ravichandran, R., Balch, T.: Value-based action selection for exploration and mapping with robot teams. In: Proc. of the IEEE Int. Conf. on Robotics & Automation (ICRA), pp. 4090–4197, New Orleans, 2004
Torralba, A., Murphy, K., Freeman, W., Rubin, M.: Context-based vision system for place and object recognition. In: Proc. of the Int. Conf. on Computer Vision (ICCV), Nice, 2003
Viola, P., Jones, M.J.: Robust real-time object detection. In: Proc. of IEEE Workshop on Statistical and Theories of Computer Vision, Vancouver, 2001
Yamauchi, B.: Frontier-based exploration using multiple robots. In: Proc. of the Second International Conference on Autonomous Agents, pp. 47–53, Minneapolis, 1998
Yamauchi, B., Schultz, A., Adams, W.: Integrating exploration and localization for mobile robots. Adapt. Behav. 7(2), 217–229 (1999)
Zelinsky, A., Jarvis, R., Byrne, J., Yuta, S.: Planning paths of complete coverage of an unstructured environment by a mobile robots. In: Proc. of the Int. Conf. on Advanced Robotics (ICAR), pp. 533–538, Tokyo, 1993
Zlot, R., Stenz, A.T., Dias, M.B., Thayer, S.: Multi-robot exploration controlled by a market economy. In: Proc. of the IEEE Int. Conf. on Robotics & Automation (ICRA), Washington, DC, 2002
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Stachniss, C., Martínez Mozos, Ó. & Burgard, W. Efficient exploration of unknown indoor environments using a team of mobile robots. Ann Math Artif Intell 52, 205–227 (2008). https://doi.org/10.1007/s10472-009-9123-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-009-9123-z