Multi Robot Exploration through Pruning Frontiers

Abstract:

In this paper, an approach to multi robot exploration is presented. One of the key issues in multi robot exploration is how to assign target locations to the individual robots and how to better distribute the robots over the environment. The proposed technique applies a well-known unsupervised clustering algorithm (k-means) in order to fairly divide the space into as many disjoint regions as available robots. Hungarian Method is used for the assignment of robots to the individual regions with the task to explore the corresponding area. To drive the robots around the environment, a frontier ‘regions on the boundary between open space and unexplored space’ based navigation strategy is used to decide where to move next, according to the data collected so far. Furthermore, we discuss improvements to the frontier based exploration strategy, by pruning the frontier cells that further reduces the computational time. The numbers of candidate locations are evaluated based on three criteria: number of unknown cells, number of known cells and real path travelling cost. Simulations are presented to show the performance of the proposed technique. This method can best be applied in search and rescue operations, partitioning helps to explore different regions of the workspace parallely by different robots instead of concentrating efforts in particular spot, pruning helps to make movement decisions much faster, the result is that the potential victims in a region will not have to wait much longer.

• Periodical: Advanced Materials Research (Volume 462)
• Pages: 609-616
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.462.609
• Online since: February 2012
• Authors: Anshika Pal, Ritu Tiwari, Anupam Shukla
• Keywords: Area Exploration, Frontiers, Hungarian Method, K-Mean, Multi-Robot System, Unsupervised Clustering

References

[1] D. Fox, J. Ko, K. Konolige, B. Limketkai, D. Schulz, and B. Stewart, Distributed multirobot exploration and mapping, Proceedings of the IEEE, vol. 94, no. 7, 2006, p.1325–1339.

DOI: 10.1109/jproc.2006.876927

[2] B. Yamauchi, Frontier-based exploration using multiple robots, Proceedings of the International Conference on Autonomous Agents, 1998, pp.47-53.

DOI: 10.1145/280765.280773

[3] W. Burgard et al., Collaborative multi-robot exploration, Proceedings of the International Conference on Robotics and Automation, vol. 1, 2000, pp.476-481.

[4] W. Burgard, M. Moors, C. Stachniss, F. Schneider, Coordinated multi robot exploration, IEEE Transactions on Robotics, vol. 21, no. 3, 2005, pp.376-386.

DOI: 10.1109/tro.2004.839232

[5] D. Latimer, et al, Towards sensor based coverage with robot teams, IEEE International Conference on Robotics and Automation, 2002, pp.961-967.

[6] B. Yamauchi, Decentralized coordination for multirobot exploration, Robotics and Autonomous Systems, Vol. 29, 1999, pp.111-118.

DOI: 10.1016/s0921-8890(99)00046-9

[7] S. S. Ge, C. H. Fua, Complete Multi-Robot Coverage of Unknown Environments with Minimum Repeated Coverage, IEEE International Conference on Robotics and Automation, 2005, pp.727-732.

DOI: 10.1109/robot.2005.1570202

[8] A. Howard, M. J. Mataric and G. S. Skhatme, Mobile sensor network deployment using potential fields: a distributed, scalable solution to the area coverage problem, 6th Int. Symp. on Distributed Autonomous Robotics Systems, 2002, pp.299-308.

DOI: 10.1007/978-4-431-65941-9_30

[9] A. Solanas, M. A. Garcia, Coordinated multi-robot exploration through unsupervised clustering of unknown space, Proc. Int. Conf. on Intelligent Robots and Systems, vol. 1, 2004, pp.717-721.

DOI: 10.1109/iros.2004.1389437

[10] Ling Wu, et al, Balanced Multi-Robot Exploration through a Global Optimization Strategy, Journal of Physical Agents, vol. 4, no. 1, (2010).

[11] J.A. Hartigan and M.A. Wong, A k-means clustering algorithm, Journal of Applied Statistics, vol. 28, 1979, pp.100-108.

[12] http: /www. computerrobotvision. org/slam_camp/ufkes_PathfindingTutorial. pdf.

[13] Anupam Shukla, Ritu Tiwari, Rahul Kala, Real Life Applications of Soft Computing, CRC Press Taylor & Fransis Group, (2010).

[14] H.W. Kuhn, The hungarian method for the assignment problem, Naval Research Logistics Quarterly, vol. 2, no. 1, 1955, p.83–97.

DOI: 10.1002/nav.3800020109

[15] H. Choset, Coverage for robotics—a survey of recent results, Ann. Math. Artif. Intell., vol. 31, no. 1, 2001, p.113–126.

[16] J. Rogge, D. Aeyels, A novel strategy for exploration with multiple robots, Proceedings of the 4th International Conference on Informatics in Control, Automation and Robotics, Angers, (2007).

[17] M. Al-Khawaldah, S. Livatino, D. Lee, Frontier based exploration with two Cooperative Mobile Robots, International Journal of Circuit, Systems and Signal Processing, Issue 2, Vol. 4, (2010).

DOI: 10.1109/isie.2010.5637085

[18] A. W. Stroupe, R. Ravichandran, T. Balch, Value-based action selection for exploration and mapping with robot teams, Proc. of the IEEE Int. Conf. on Robotics & Automation (ICRA), p.4090–4197, (2004).

DOI: 10.1109/robot.2004.1308930

[19] M. J. Matari´c, G. Sukhatme, Task-allocation and coordination of multiple robots for planetary exploration, Proc. of the Int. Conf. on Advanced Robotics (ICAR), p.61–70, (2001).

[20] R. Menezes, F. Martins, F. E. Vieira, R. Silva, M. Braga, A model for terrain coverage inspired by ant's alarm pheromones, Proceedings of the 2007 ACM symposium on Applied computing, 2007, p.728–732.

DOI: 10.1145/1244002.1244164

[21] Kai M. Wurm, et al, Coordinated Multi-robot Exploration using a Segmentation of the Environment, International conference on Intelligent Robots and Systems, (2008).

DOI: 10.1109/iros.2008.4650734