Multiple Mobile Robot Exploration and Patrol Strategy Using a Self-Organizing Planner Based on a Reaction-Diffusion Equation on a Graph
Chomchana Trevai, Norisuke Fujii, Jun Ota,
and Tamio Arai
The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan
In this paper, we propose a search and surveillance with mobile robots to collect information while minimizing repeated coverage to maximize efficiency. The problem of search and surveillance is defined as one having a mobile robot or covering a working area with sensor footprints. The problem is applicable to tasks such as floor cleaning, map building, surveillance, security patrols, and search and rescue operations. We use a reaction-diffusion equation on a graph (RDEG), we make and remake plans online base on incoming environmental information. The strategy is applicable to patrolling tasks after an environment has been completely explorated. Tasks are allocated to multiple mobile robots, among which a temporary leader, i.e., the robot detecting a drastic change in the environment, plans a strategy for other mobile robots on the team. Sensing and positioning data for each robot is broadcast and shared among robots. Simulation in different scenarios using one to three robots demonstrated the feasibility of increasing the number of robots on a team.
-  H. Choset, “Coverage for Robotics – A Survey of Recent Results,” Annals of Mathematics and Artificial Intelligence, Vol.31, pp. 113-126, 2001.
-  D. Latimer IV, S. Srinivasa, V. Lee-Shue, S. Sonne, H. Choset, and A. Hurst, “Towards Sensor-Based Coverage with Robot Teams,” In Proc. of IEEE Int. Conf. on Robotics & Automation, pp. 961-967, Washington DC, May, 2002.
-  S. J. Moorehead, R. Simmons, and W. L. Whittaker, “Autonomous Exploration Using Multiple Sources of Information,” In Proc. of the IEEE Int. Conf. on Robotics & Automation (ICRA), pp. 3098-3103, 2001.
-  B. Yamauchi, “Frontier-Based Exploration Using Multiple Robots,” In Proc. of Second Int. Conf. on Autonomous Agents, pp. 47-53, 1998.
-  B. Yamauchi, A. Schultz, and W. Adams, “Integrating Exploration and Localization for Mobile Robots,” Adaptive Systems, 7(2), 1999.
-  W. Burgard,M.Moors, D. Fox, R. Simmons, and S. Thrun, “Collaborative Multi-Robot Exploration,” In Proc. of Int. Conf. on Robotics and Automation (ICRA), pp. 476-481, 2000.
-  W. Burgard, M. Moors, and F. Schneider, “Collaborative Exploration of Unknown Environments with Teams of Mobile Robots,” In M. Beetz, J. Hertzberg, M. Ghallab, and M. E. Pollack (Eds.), Advances in Plan-Based Control of Robotic Agents, Springer Verlag, Vol.2466 of Lecture Notes in Computer Science, pp. 52-70, 2001.
-  R. Simmons, D. Apfelbaum, W. Burgard, D. Fox, M. Moors, S. Thrun, and H. Younes, “Coordination for Multi-Robot Exploration and Mapping,” In Proc. of the National Conf. on Artificial Intelligence AAAI, pp. 852-858, 2000.
-  C. Trevai, Y. Fukazawa, H. Yuasa, J. Ota, T. Arai, and H. Asama, “Exploration Path Generation for Multiple Mobile Robots Using a Reaction-Diffusion Equation on a Graph,” In special issue of Integrated Computer-Aided Engineering (ICAE), pp. 1114-1119, 2004.
-  H. P. Moravec and A. E. Elfes, “High-Resolution Maps from Wide-Angle Sonar,” In Proc. of IEEE Int. Conf. on Robotics and Automation, pp. 116-121, 1985.
-  A. Elfes, “Using Occupancy Grids forMobile Robot Perception and Navigation,” IEEE Computer, 22(6), pp. 46-57, 1989.
-  A. Elfes, “Sonar-Based Real-World Mapping and Navigation,” in IEEE J. Robotics and Automation, RA3, pp. 249-265, June, 1987.
-  D. Kurabayashi, J. Ota, T. Arai, and E. Yoshida, “An Algorithm of Dividing a Work Area to Multiple Mobile Robots,” In Proc. of IEEE/RSJ Int. Conf. on Intelligence Robots and Systems, 2, pp. 286-291, 1995.
-  J. C. Latombe, “Robot motion planning,” Kluwer Academic Publishers, 1991.
-  Y. Gabriely and E. Rimon, “Spanning-Tree-Based Coverage of Contiguous Areas by a Mobile Robot,” In Proc. of IEEE Int. Conf. on Robotics and Automation, pp. 1927-1933, 2001.
-  E. González, A. Suárez, C. Moreno, and F. Artigue, “Complementary Regions: A Surface Filling Algorithm,” In Proc. of IEEE Int. Conf. on Robotics and Automation, pp. 909-914, 1996.
-  J. B. Mellisen and P. C. Shuur, “Covering a Rectangle with Six and Seven Circles,” In Discreet Applied Mathematics, 14, pp. 149-156, 2000.
-  H. Yuasa and M. Ito, “Self-Organizing System Theory by Use of Reaction-Diffusion Equation on a Graph with Boundary,” In Proc. of IEEE Int. Conf. on System, Man, and Cybernetics, pp. 211-216, 1999.
-  H. Yuasa and M. Ito, “Internal Observation Systems and a Theory of Reaction-Diffusion Equation on a Graph,” In Proc. of IEEE Intern. Conf. on Systems, Man, and Cybernetics, pp. 3669-3673, 1998.
-  Y. Fukazawa, C. Trevai, J. Ota, H. Yuasa, T. Arai, H. Asama, and K. Kawabata, “Realizing the Exploration and Rearrangement Task of Multiple Unknown Objects by an Actual Mobile Robot,” In Advanced Robotics, 19, 1, pp. 1-20, 2005.
-  C. Trevai, Y. Fukazawa, J. Ota, H. Yuasa, T. Arai, and H. Asama, “Cooperative Exploration of Mobile Robots Using a Reaction-Diffusion Equation on a Graph,” In Proc. of IEEE Int. Conf. on Robotics and Automation (ICRA2003), pp. 2269-2274, 2003.
-  M. B. Dias and A. Stentz, “A Free Market Architecture for Distributed Control of a Multi-Robot System,” In 6th Int. Conf. on Intelligent Autonomous Systems (IAS-6), pp. 115-122, 2000.
-  E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, “The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization,” John Wiley & Sons, 1985.
-  D. Hochbaum, “Approximation Algorithms for NP-hard Problems,” PWS Publishing Company, 1997.
-  B. P. Gerkey, R. T. Vaughan, K. Stoy, A. Howard, M. J. Mataric, and G. S. Sukhatme, “Most Valuable Player: A Robot Device Server for Distributed Control,” In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pp. 1226-1231, Vailea, Hawaii, October, 2001.
-  R. T. Vaughan, B. P. Gerkey, and A. Howard, “On Device Abstractions for Portable, Reusable Robot Code,” In Proc. of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pp. 2121-2127, Las Vegas, Nevada, October, 2003.
-  B. P. Gerkey, R. T. Vaughan, and A. Howard, “The Player/Stage Project: Tools for Multi-Robot and Distributed Sensor Systems,” In Proc. of the Int. Conf. on Advanced Robotics (ICAR), pp. 317-323, Coimbra, Portugal, July, 2003.
-  C. Trevai, R. Takemoto, Y. Fukazawa, J. Ota, and T. Arai, “Local Obstacle Avoidance with Reliable Goal Acquisition for Mobile Robots,” Distributed Autonomous Robotics Systems, 6, Springer, pp. 41-50, 2004.
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.
Copyright© 2008 by Fuji Technology Press Ltd. and Japan Society of Mechanical Engineers. All right reserved.