We present the method of exploration using environmental boundary information for an indoor map generation problem of a mobile robot. We introduce an exploration method by (i) integration of the exploration method with Reaction-Diffusion Equation on a Graph (RDEG) and connected components labeling and (ii) a replanning framework in updating exploration plan for the currently obtained sensor information. Our approach has been implemented in simulation environments and has been compared with two existing methods: frontier-based exploration method and zig-zag method. The results demonstrate the efficiency of our approach over others. Lastly, the approach was implemented and tested on an actual robot, demonstrating its efficiency in a real-world situation. 1. Introduction Currently, an autonomous mobile robot needs to possess three important properties. They are the ability to efficiently explore an environment, to develop a map of the environment, and to automatically self-localize on the map. An exploration plan is the guideline for the robot to identify the location of obstacles, objects, and free spaces effectively by sensing the environment. Robot tasks, such as searching, require time and energy and, thus, an effective exploration plan is required for a robot to complete the task in a fast and energy-efficient manner. Without an efficient exploration plan, the robot might move inefficiently, wasting time and energy in unproductive searching. Exploration is a basis for many other applications. One important application is mapping an unknown area to create a representation of the environment to be explored. Many successful robot systems rely on maps. The mapping problem is constantly interleaved with decision making involving the next move. A robot moving along the points to observe an environment area in a minimum amount of time is already an NP-hard problem [1–3]. In an actual environment, robots often encounter unanticipated obstacles that make it difficult to complete a task. To deal with such situations, robots replan exploration paths to avoid obstacles while acquiring a wide and effective sensing range in an unexplored area. In addition, replanning happens several times, since unknown obstacles are frequently encountered in real environments. Therefore, a good exploration plan also includes a good replanning algorithm that must be simple, effective, and computationally efficient. Here, what we need to consider is that, in many cases, we have the information of environmental boundary in advance, such as cleaning or patrolling tasks. For example,
References
[1]
E. L. Lawler, J. K. Lenstra, A. H. G. Rinooy Kan, and D. B. Shumoys, The Traveling Salesman Problem—A Guided Tour of Combinatorial Optimization, Wiley-Interscience, New York, NY, USA, 1985.
[2]
J. K. Lenstra and A. H. G. R. Kan, “On general routing problems,” Networks, vol. 6, pp. 273–280, 1976.
[3]
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP Completeness, W.H. Freeman, New York, NY, USA, 1979.
[4]
B. Yamauchi, “Decentralized coordination for multirobot exploration,” Robotics and Autonomous Systems, vol. 29, no. 2, pp. 111–118, 1998.
[5]
H. Choset, Sensor based motion planning: the hierarchical generalized Voronoi Graph [Ph.D. thesis], California Institue of Technology, Pasadena, Calif, USA, 1996.
[6]
R. Simmons, D. Apfelbaum, W. Burgard et al., “Coordination for multirobot exploration and mapping,” in Proceedings of the 17th National Conference on Artificial Intelligence (AAAI '00), pp. 852–858, September 2000.
[7]
W. Burgard, D. Fox, M. Moors, R. Simmons, and S. Thrun, “Collaborative multi-robot exploration,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA '00), pp. 476–481, April 2000.
[8]
A. Mobarhani, S. Nazari, A. H. Tamjidi, and H. D. Taghirad, “Histogram based frontier exploration,” in Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS '11), pp. 1128–1133, September 2011.
[9]
B. Tovar, L. Mu？oz-Gómez, R. Murrieta-Cid, M. Alencastre-Miranda, R. Monroy, and S. Hutchinson, “Planning exploration strategies for simultaneous localization and mapping,” Robotics and Autonomous Systems, vol. 54, no. 4, pp. 314–331, 2006.
[10]
L. Freda and G. Oriolo, “Frontier-based probabilistic strategies for sensor-based exploration,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA '05), pp. 3881–3887, Barcelona, Spain, April 2005.
[11]
A. Mobarhani, S. Nazari, A. H. Tamjidi, and H. D. Taghirad, “Histogram based frontier exploration,” in Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems: Celebrating 50 Years of Robotics (IROS '11), pp. 1128–1133, San Francisco, Calif, USA, September 2011.
[12]
R. A. Prieto, J. M. Cuadra-Troncoso, J. R. álvarez-Sánchez, and I. N. Navarro-Santosjuanes, “Reactive navigation and online SLAM in autonomous frontierbased exploration,” in Natural and Artificial Computation in Engineering and Medical Applications, vol. 7931 of Lecture Notes in Computer Science, pp. 45–55, Springer, Berlin, Germany, 2013.
[13]
W. Burgard, M. Moors, C. Stachniss, and F. E. Schneider, “Coordinated multi-robot exploration,” IEEE Transactions on Robotics, vol. 21, no. 3, pp. 376–386, 2005.
[14]
Y. Fukazawa, T. Chomchana, J. Ota, H. Yuasa, T. Arai, and H. Asama, “Region exploration path planning for a mobile robot expressing working environment by grid points,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA '03), pp. 2448–2454, Taipei, Taiwan, September 2003.
[15]
C. Trevai, K. Ichikawa, Y. Fukazawa et al., “Real-time cooperative exploration by reaction-diffusion equation on a graph,” in Proceedings of the International Symposium on Distributed Autonomous Robotic Systems (DARS '02), pp. 383–392, 2002.
[16]
J.-C. Latombe, Robot Motion Planning, Kluwer Academic, New York, NY, USA, 1991.
[17]
H. Choset, E. Acar, A. A. Rizzi, and J. Luntz, “Exact cellular decompositions in terms of critical points of Morse functions,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA '00), pp. 2270–2277, April 2000.
[18]
Z. L. Cao, H. Huang, and E. L. Hall, “Region filling operations with random obstacle avoidance for mobile robots,” Journal of Robotic Systems, vol. 5, no. 2, pp. 87–102, 1988.
[19]
H. Yuasa and M. Ito, “Internal observation systems and a theory of reaction-diffusion equation on a graph,” in Proceedings of the 1998 IEEE International Conference on Systems, Man, and Cybernetics, pp. 3669–3673, October 1998.
[20]
QR Code.com, http://www.qrcode.com/en/index.html.
[21]
T. Wattanavekin and J. Ota, “Exploration in a boundary environment with unknown obstacles using Reaction-Diffusion equation on a graph,” in Proceedings of the IEEE International Conference on Robotics and Biomimetics, pp. 2623–2628, Tokyo, Japan, 2011.
[22]
S. Lin and B. W. Kernighan, “An effective heuristic algorithm for the traveling-salesman problem,” Operations Research, vol. 21, no. 2, pp. 498–516, 1973.
[23]
A. Rosenfeld and J. L. Pfaltz, “Sequential operations in digital processing,” Journal of the ACM, vol. 13, pp. 471–494, 1966.
[24]
H. A. Eiselt, M. Gendreau, and G. Laporte, “Arc routing problems, part II: the rural postman problem,” Operations Research, vol. 43, no. 3, pp. 399–414, 1995.
[25]
M. J. Todd, G. L. Lemhauser, and A. H. G. R. Kan, “The traveling salesman problem,” in Handbooks in Operations Research and Management Science, vol. 7, pp. 527–562, Elsevier Science, Amsterdam, The Netherlands, 1989.
[26]
N. Fujii, R. Inoue, Y. Takebe, and J. Ota, “Multiple robot rearrangement planning using a territorial approach and an extended project scheduling problem solver,” Advanced Robotics, vol. 24, no. 1-2, pp. 103–122, 2010.
[27]
S. Thrun, W. Burgard, and D. Fox, Probabilistic Robotics, The MIT press, Cambridge, Mass, USA, 2005.
[28]
G. Grisetti, C. Stachniss, and W. Burgard, “Improved techniques for grid mapping with Rao-Blackwellized particle filters,” IEEE Transactions on Robotics, vol. 23, no. 1, pp. 34–46, 2007.
[29]
M. Quigley, B. Gerkey, K. Conley et al., “ROS: an open-source robot operating system,” in Proceedings of the Opensource Software Workshop of International Conference on Robotics and Automation (ICRA '09), 2009.
