IJE TRANSACTIONS A: Basics Vol. 32, No. 4 (April 2019) 608-616    Article in Press

PDF URL: http://www.ije.ir/Vol32/No4/A/20-3060.pdf  
downloaded Downloaded: 30   viewed Viewed: 133

S. Hadian Jazi, S. Farahani and H. Karimpour
( Received: October 16, 2018 – Accepted: March 07, 2019 )

Abstract    In this article, a fast and reliable map-merging algorithm is proposed to produce a global two dimensional map of an indoor environment in a multi-robot simultaneous localization and mapping (SLAM) process. In SLAM process, to find its way in this environment, a robot should be able to determine its position relative to a map formed from its observations. To solve this complex problem, simultaneous localization and mapping methods are required. In large and complex environments, using a single robot is not reasonable because of the error accumulation and the time required. This can explain the tendency to employ multiple robots in parallel for this task. One of the challenges in the multi-robot SLAM is the map-merging problem. A centralized algorithm for map-merging is introduced in this research based on the features of local maps and without any knowledge about robots initial or relative positions. In order to validate the proposed merging algorithm, a medium scale experiment has been set up consisting of two heterogeneous mobile robots in an indoor environment equipped with laser sensors. The results indicate that the introduced algorithm shows good performance both in accuracy and fast map-merging.


Keywords    Map-merging; Multi-agents Simultaneous Localization and Mapping; Ground Robot; Image Processing



در این مقاله یک آلگوریتم ترکیب نقشه سریع و قابل اعتماد برای تولید نقشه کلی از یک محیط داخلی و در یک پروسه نقشه‌برداری و تعیین موقعیت همزمان چند رباتی ارائه شده‌است. یک ربات برای حرکت در یک محیط و پیدا کردن مسیر حرکت خود به نقشه‌ای از محیط نیاز دارد و همچنین برای تهیه نقشه از محیط به موقعیت خود در آن محیط وابسته است. این مساله یچیده را نقشه‌برداری و تعیین موقعیت همزمان می‌گویند. در محیط‌های بزرگ و پیچیده، به دلایل متفاوتی از جمله انباشتگی خطا و طولانی‌شدن پروسه، استفاده از یک ربات برای نقشه‌برداری توجیه‌پذیر نیست. در این موارد معمولا از چند ربات برای این کار استفاده می‌شود. یکی از مهمترین چالشها در پروسه‌های چندرباتی نقشه‌برداری، ترکیب‌کردن نقشه‌های محلی تهیه‌شده توسط هر ربات از محیط و یا بخشی از آن و سپس تولید نقشه کلی آن محیط است. در این مقاله یک آلگوریتم مرکزی برای ترکیب نقشه بر پایه ویژگی‌ها و مشخصه‌های نقشه‌های محلی ارائه می‌شود که در آن به اطلاعاتی از قبیل موقعیت اولیه یا موقعیت نسبی ربات‌ها نیازی نیست. به‌منظور ارزشیابی این آلگوریتم به‌صورت تجربی از دو ربات متفاوت که به سنسورهای لیزری متفاوتی برای پویش محیط مجهز هستند می‌شود. نتایج آزمایش نشان می‌دهد که آلگوریتم معرفی‌شده دقت و سرعت مناسبی برای ترکیب‌کردن نقشه‌های محلی و تولید نقشه کلی از محیط دارد.


1. Rone, W. and Ben-Tzvi, P., “Mapping, localization and motion planning in mobile multi-robotic systems,” Robotica, Vol. 31, No. 1, (2013), 1–23.
2. Fenwick, J. W., Newman, P. M., and Leonard, J. J., "Cooperative concurrent mapping and localization", in 2002 IEEE International Conference on Robotics and Automation, (2002), 1810–1817.
3. Konolige, K., Fox, D., Ortiz, C., Agno, A., Eriksen, M., Limketkai, B., Ko, J., Morisset, B., Schulz, D., Stewart, B., and Vincent, R., “Centibots: Very large scale distributed robotic teams,” Springer Tracts in Advanced Robotics, Vol. 21, No. 1, (2006), 131–140.
4. Thrun, S., “A Probabilistic On-Line Mapping Algorithm for Teams of Mobile Robots,” The International Journal of Robotics Research, Vol. 20, No. 5, (2001), 335–363.
5. Williams, S. B., Dissanayake, G., and Durrant-Whyte, H., "Towards multi-vehicle simultaneous localisation and mapping", in Proceedings 2002 IEEE International Conference on Robotics and Automation, Vol. 3, 2743–2748, (2002).
6. Thrun, S. and Liu, Y., “Multi-robot SLAM with sparse extended information filers,” Robotics Research, Vol. 15, No. 1, (2005), 254–266.
7. Carpin, S., Birk, A., and Jucikas, V., “On Map Merging,” International Journal of Robotics and Autonomous Systems, Vol. 53, No. 1, (2005), 1–14.
8. Birk, A. and Carpin, S., "Merging Occupancy Grid Maps From Multiple Robots", in Proceedings of the IEEE, Vol. 94, No. 7, 1384–1397, (2006).
9. Saeedi, S., Paull, L., Trentini, M., and Li, H., “Neural Network-Based Multiple Robot Simultaneous Localization and Mapping,” IEEE Transactions on Neural Networks, Vol. 22, No. 12, (2011), 2376–2387.
10. Saeedi, S., Paull, L., Trentini, M., Seto, M., and Li, H., "Efficient map merging using a probabilistic generalized Voronoi diagram", in 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, 4419–4424, (2012).
11. Dinnissen, P., Givigi, S. N., and Schwartz, H. M., "Map merging of Multi-Robot SLAM using Reinforcement Learning", in 2012 IEEE International Conference on Systems, Man, and Cybernetics (SMC), 53–60, (2012).
12. Li, H., Tsukada, M., Nashashibi, F., and Parent, M., “Multivehicle cooperative local mapping: A methodology based on occupancy grid map merging,” IEEE Transactions on Intelligent Transportation Systems, Vol. 15, No. 5, (2014), 2089–2100.
13. Park, J., Sinclair, A. J., Sherrill, R. E., Doucette, E. A., and Curtis, J. W., "Map merging of rotated, corrupted, and different scale maps using rectangular features", in 2016 IEEE/ION Position, Location and Navigation Symposium (PLANS), 535–543, (2016).
14. Park, J., "A Reduced Element Map Representation and Applications: Map Merging, Path Planning, and Target Interception". PhD Thesis: Aerospace Engineering, Auburn University, (2017).
15. Ahn, J. G. and Jeon, H. S., "R-Map : A Hybrid Map Created by Maximal Rectangles", in ICCAS 2010, 1336–1339, (2010).
16. Lowe, D. G., “Distinctive image features from scale-invariant keypoints,” International journal of computer vision, Vol. 60, No. 2, (2004), 91–110.
17. Harris, C. and Stephens, M., "A combined corner and edge detector.", in Proceedings of Fourth Alvey vision conference, Vol. 15, No. 50, 147–151, (1988).
18. Fischler, M. A. and Bolles, R. C., “Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography,” Communications of the ACM, Vol. 24, No. 6, (1981), 381–395. 

Download PDF 

International Journal of Engineering
E-mail: office@ije.ir
Web Site: http://www.ije.ir