本篇論文係透過機器人搭載雷射測距儀，連續地搜集環境中機器人與障礙物之間的距離資訊，並將距離資訊轉換為座標集合，再藉由迭代最近點演算法(Iterative Closest Point, ICP)將座標點集合疊合為一張地圖。由於傳統迭代最近點演算法容易受到資料的初始位置影響而造成建圖錯誤，且隨著建圖進行，資料量逐漸增加也會導致了運算時間的增長。故本論文提出ㄧ權重式連續型ICP演算法，利用機器人在連續搜集距離資訊時，相鄰兩筆資料差異不大的特性，使用相鄰的資料進行ICP演算法，再利用前幾組座標集合計算出的旋轉量、位移量以修正當前集合的位置並與全域地圖重合，藉由更新當前集合再修正集合位置的方法，避免了因初始位置差距過大而導致的建圖錯誤，同時降低了與全域地圖運算的資料量，也透過兩次的ICP運算，提出了改良式權重連續型ICP演算法以進一步提高運算的精準度。最後將此序列式演算法，透過雲端架構修改為分散式平行架構，將ICP演算法中大量使用的迴圈運算的步驟分散給雲端叢集處理，以降低運算的負擔，提高運算效能。

This paper proposes a method of map building based on cloud-computing with a weighted iterative closest point (ICP) algorithm, in which a laser range finder is used to measure the distance between the robot and obstacles. Previously, after converting these data into cloud point sets, the traditional ICP could be used to align two of these sets. However, two problems exist with this method. Firstly, its efficiency and accuracy can be affected by outliers and noises. Secondly, the model set continues to grow during the ICP process. Therefore, this paper proposes continuous alignment to solve these problems. We take one cloud point set and another set of the next generation to build the map; because these sets share a higher similarity than the sets used in the traditional ICP, higher accuracy can be achieved. Besides, as the continuous ICP proposed by this paper has a fixed reference set, in contrast to the traditional ICP with a growing set, time consumption is also improved. In addition, a modified continuous ICP algorithm is introduced to reduce errors. Finally, cloud computing architecture is used to realize parallel computing for reduction of computational burdens.

[1] 米家掃地機器人, https://www.mi.com/tw/mi-robot-vacuum/
[2] BigDog, https://www.bostondynamics.com/bigdog
[3] Amazon Web Service, https://aws.amazon.com/tw
[4] P. Besl and N. McKay, “A Method for Registration of 3-D Shapes,” IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI)., vol. 14, no. 2, pp. 239-256, Feb. 1992.
[5] S. Rusinkiewicz and M. Levoy, “Efficient Variants of the ICP Algorithm,” in Proc. 3-D Digital Imaging and Modeling (3DIM)., CA, 2001. pp. 145-152.
[6] G. Turk and M. Levoy, “Zippered Polygon Meshes from Range Images,” in Proc. SIGGRAPH’94., Orlando, FL, July. 1994. pp. 311-318.
[7] T. Masuda, K. Sakaue and N. Yokoya, “Registration and Integration of Multiple Range Images for 3-D Model Construction,” in Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)., San Francisco, CA, Jun. 1996. pp. 879-883.
[8] M. Greenspan and M. Yurick, “Approximate K-D Tree Search for Efficient ICP,” in Proc. 4th International Conf. on 3-D Digital Imaging and Modeling (3DIM’03)., Banff, Canada, Oct. 2003, pp. 442-448.
[9] Y. Chen and G. Medioni, “Object Modeling by Registration of Multiple Range Images,” in Proc. IEEE Conf. on International Conference on Robotics and Automation (ICRA)., Sacramento, CA, Apr. 1991, pp. 2724-2729.
[10] G. Godin, M. Rioux and R. Baribeau, “Three-dimensional registration using range and intensity information,” in Proc. SPIE vol. 2350:Videometrics III., Boston, MA, pp. 279-290, 1994.
[11] K. Pulli, “Multiview Registration for Large Data Sets,” in Proc. 2nd International Conf. on 3-D Digital Imaging and Modeling (3DIM)., Ottawa, Canada, Oct. 1999, pp. 160-168.
[12] K. Arun, T. Huang and S. Blostein, “Least-Squares Fitting of Two 3-D Point Sets,” IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI)., vol. 9, no. 5, pp. 698-700, Sep. 1987.
[13] B. Horn, “Closed-form solution of absolute orientation using unit quaternions,” in Proc. Journal of the Optical Society of America A (JOSAA), vol. 4, no. 4, pp. 629-642, 1987.
[14] B. Horn, H. Hilden and S. Negahdaripour, “Closed-Form Solution of Absolute Orientation Using Orthonormal Matrices,” in Proc. Journal of the Optical Society of America A (JOSAA), vol. 5, no. 7, pp. 1127-1135, 1988.
[15] M. Walker, L. Shao and R. Volz, “Estimating 3-D location parameters using dual number quaternions,” in Proc. CVGIP: Image Understanding, vol. 54, no. 3, pp.358-367, 1991.
[16] A. Segal, D. Haehnel and S. Thrun, “Generalized-ICP,” in Proc. Robotics: Science and Systems (RSS), Seattle, WA, June. 2009, pp. 26–27.
[17] Z. Zhang, “Iterative Point Matching for Registration of Free-Form Curves and Surfaces,” in Proc. International Journal of Computer Vision, vol. 13 no. 2 pp. 119–152, 1994.
[18] G. Penney, P. Edwards, A. King, J. Blackall, P. Batchelor and D. Hawkes, “A Stochastic Iterative Closest Point Algorithm (stochastic ICP),” in Proc. International Conf. on Medical Image Computing and Computer Assisted Intervention (MICCAI), Heidelberg, Germany, Oct. 2001, pp. 762–769.
[19] O. Sorkine-Hornung and M. Rabinovich, “Least-Squares Rigid Motion Using SVD,” Technical Report, Jan. 2017, pp. 1-5.
[20] D.-J. Lee, Y.-M. Yun, Y.-S. Hwang and J.-M. Lee, “2D grid map building using ICP algorithm and line extraction,” in Proc. 14th International Conference on Control, Automation and Systems (ICCAS), Seoul, South Korea, Oct. 2014, pp. 852-855.
[21] C.-C. Hsu, H.-E. Chang and Y.-Y. Lu, “Map building of unknown environment using PSO-tuned enhanced iterative closest point algorithm,” in Proc. IEEE Conf. on International Conference on System Science and Engineering (ICSSE), Budapest, Hungary, Jul. 2013, pp.279-284.
[22] S. Ghemawat, H. Gobioff and S.-T. Leung, “The google file system,”in Proc. of ACM Symposium on Operating Systems Principles, Lake George, NY, Oct. 2003. pp.29-43.
[23] J. Dean and S. Ghemawat, “MapReduce: simplified data processing on large clusters,” in Proc. Operating System Design and Implementation (OSDI), San Francisco, CA, Dec. 2004, pp. 107-113
[24] F. Chang, J. Dean, S. Ghemawat, W. Hsieh, D. Wallach, M. Burrows, T. Chandra, A. Fikes and R. Gruber, “Bigtable: a distributed storage system for structured data,” in Proc. Operating System Design and Implementation (OSDI), Seattle, WA, Nov. 2006, pp.205-218
[25] 林大貴，Python+Spark 2.0+Hadoop機器學習與大數據分析實戰，新北市，2016.
[26] K. Shvachko, H. Kuang, S. Radia and R. Chansler, “The Hadoop Distributed File System,” in Proc. Mass Storage Systems and Technologies (MSST), Incline Village, NV, Jun, 2010. pp. 1-10.
[27] HDFS, https://hadoop.apache.org/docs/r2.6.0/hadoop-project-dist/hadoop-hdfs/HdfsDesign.html
[28] M. Zaharia, M. Chowdhury, M.Franklin, S. Shenker and I. Stoica, “Spark: cluster computing with working sets,” in Proc. USENIX workshop on Hot Topics in Cloud Computing, Boston, MA, Jun. 2010 pp. 10-16.
[29] Generality of Spark, https://spark.apache.org/
[30] 顏愷君，“基於ROS分散式架構之履帶式機器人跨樓層巡邏功能設計與實現”，國立臺灣師範大學電機工程學系系碩士論文，106年7月。
[31] SICK LMS-100-10000, https://www.sick.com/tw/zf/detection-and-ranging-solutions/2d-lidar/lms1xx/lms100-10000/p/p109841