指導教授：黃漢邦臺灣大學：機械工程學研究所翁振虔Ung, Chin-YihChin-YihUng2014-11-292018-06-282014-11-292018-06-282013http://ntur.lib.ntu.edu.tw//handle/246246/263163為了要使得機器人更容易被人們所接受，機器人必須理解環境中的人類行為。在不久的將來，機器人將頻繁出現在人類生活環境中，像是學校、醫院、辦公大樓、博物館、以及一般家庭等等區域，因此動態環境評估預測變得很重要。而排隊為人類社會最常見的行為之一，所以機器人必須學習相關的知識。 個人化服務型機器人是人類社會的下個趨勢，機器人為了能提供擁有者更便利舒適的生活，在到達服飾店門口時，會下載服飾店所提供的衣物3D模型，並可供主人快速試穿的演算法。此外，幫助主人跑腿、買東西、付賬等更是基本功能，因此機器人能夠了解人與人群之間相互關係的排隊行為是急需探討的議題。此篇論文，提出了利用機率來分析動態環境行人排隊的模型，供機器人使用與人類相似的行為模型。更提出了偵測及檢測行人是否進入隊伍的演算法。排進隊伍時如何只用相機做出追蹤前方顧客及做出行動的方法。Robots need to understand the human social behaviors to interact with human correctly and to service for people in public and home environments. The way in which robots are going to live with humans has become an important issue. Therefore, estimation and prediction of dynamic human society environment are very important for robot. Standing in line is one of the most common human social behaviors and robot needs to learn it. The imminent trend for our society would be personalization of robots capable of offering services that cater to individual needs. In order to provide a more convenient way of life, the robots are able to download the 3-Dimensional models supplied by the respective apparel stores upon arrival at the entrance. In addition, codes are immediately processed so that their owners could fit the clothes efficiently. Furthermore, apart from their basic functions of replacing their owners in errands such as purchasing goods and paying the bill, they understand the importance of human interactions during the process of queuing. This paper includes the use of probability in analyzing the model of queuing under a dynamic environment. Other than that, this paper also offered formulas in detecting and predicting the situation of queues. Nevertheless, methods of using only cameras to capture and track the customer in front and react to difference of image are also part of the paper.誌謝 i 摘要 iii Abstract v List of Tables ix List of Figures xi Nomenclature xv Chapter 1 Introduction 1 1.1 Relationship between Humans and Robots 1 1.2 Scenario of the Thesis 3 1.3 Objectives and Contributions 4 1.4 Structure of the Thesis 5 Chapter 2 Background Knowledge 7 2.1 SLAM and Moving Object Tracking 7 2.1.1 Simultaneous Localization and Mapping 8 2.1.2 Moving Object Tracking 12 2.2 Frontier-based Exploration 14 2.2.1 Cognitive Mapping 14 2.2.2 Generalized Voronoi Graph 16 2.3 Pedestrian Ego Graph (PEG) 17 2.4 Social Navigation 20 Chapter 3 Virtual Fitting Room 27 3.1 High-Speed Fitting Method 27 3.2 VFR System Experimental Results 32 Chapter 4 Pay Bill Method 35 4.1 Social Behavior Forecasting Queuing Model 36 4.1.1 Probabilistic Framework 36 4.1.2 Formulation of Tracking 38 4.1.3 Formulation of Prediction 40 4.1.4 Formulation of Goals Estimation with Customer Intention 43 4.2 Queuing System 45 4.2.1 Little’s Formula 45 4.2.2 Queue System Formula 47 4.3 Preprocess and Tracking 56 4.3.1 Filter Line Method 56 4.4 Tracking Method 66 Chapter 5 Simulations and Experiments 73 5.1 Software Platform 73 5.2 Hardware Platform 74 5.3 Experimental Results 76 Chapter 6 Conclusions and Future Works 89 6.1 Conclusions 89 6.2 Future Works 90 References 93 Table 2 1 Trajectory rank 20 Table 2 2 GSEs parameters estimated from training data 26 Table 4 1 EKF model 42 Table 4 2 Algorithm for binomial index set generator 50 Table 4 3 Algorithm for connected components of skeleton map 61 Figure 1 1 Modern robots working in human society [32, 37] 2 Figure 1 2 The act of perceiving; cognizance by the senses [36] 3 Figure 1 3 Organization of thesis 5 Figure 2 1 The essential SLAM problem [5] 8 Figure 2 2 NTU history gallery (a) Mapping by odometer, (b) Mapping by SLAM 11 Figure 2 3 (a) Occupancy grid map, (b) Real scene 11 Figure 2 4 Moving object detection using laser range finder 12 Figure 2 5 Multiple moving object detection with Kinect sensor 13 Figure 2 6 Example of trajectory tracking 13 Figure 2 7 Frontier detection 15 Figure 2 8 Thinning-based GVG structure 16 Figure 2 9 B1 floor of the engineering complex building in NTU, (a) Grid map, (b) GVG skeleton map, (c) Topological map. 16 Figure 2 10 Pedestrians usually adopt similar policies to avoid other pedestrians [11] 17 Figure 2 11 (a) Pedestrian ego graph (PEG), (b) PEG can rapidly generate multiple choices of trajectory [10] 18 Figure 2 12 (a) Preliminary PEG partition: partitions in 3 layers and partition ID [10], (b) Possible Link Nodes 18 Figure 2 13 The trajectory histograms in three layers [10] 19 Figure 2 14 The histogram of the trajectory rank between 1~30 20 Figure 2 15 Spatial behavior cognition model 21 Figure 2 16 The spatial effect of static obstacles, (a) Original map, (b) Distance transform 23 Figure 2 17 Proxemics: the pictures are provided in [35] 24 Figure 2 18 (a) Personal space [35], (b) The cost function of personal space 24 Figure 3 1 On-line VFR system 3D perspective 28 Figure 3 2 The geometry of adjusting clothes scale 29 Figure 3 3 Clothes and human relation scale 30 Figure 3 4 Coordinate system 30 Figure 3 5 VFR experiment, (a~d) Scale clothes by the position of user, (e~f) Switching clothes function, (g~j) Rotate clothes by the pose of user 33 Figure 4 1 Flow chart for paying bills 35 Figure 4 2 DBNs graphic model for localization and tracking problem 37 Figure 4 3 Goal weighting estimation 42 Figure 4 4 Map classes 43 Figure 4 5 Little’s formula 46 Figure 4 6 Queue system factors 48 Figure 4 7 Queue system probability example 53 Figure 4 8 Result of traditional method 55 Figure 4 9 Result of our method 55 Figure 4 10 Statist of 612 trajectories 55 Figure 4 11 Line feature, (a)Step 1, (b)Step 2, (c)Step 3, (d)Step 4 57 Figure 4 12 Personal space in the queuing task [48] 58 Figure 4 13 Two queue line sample 59 Figure 4 14 Kernel, (a) Morphology closing, (b) Filter single point, (c) Filter small isolated point 59 Figure 4 15 Extract queue line process, (a) Original pedestrian personal cost image, (b) After two times closing skill, (c) Thinning, (d) Filter single point 60 Figure 4 16 (a) Skeleton map, (b) Connected components labeling 61 Figure 4 17 Result of connected components algorithm 62 Figure 4 18 Probability distribution of queue in line 63 Figure 4 19 Trajectories of customers which are marked two moments 64 Figure 4 20 Statistics of confirming that the customer is standing in line 65 Figure 4 21 Pedestrian personal space and queue line distribution (the time after the time of before sample) 65 Figure 4 22 Sub image of the original pedestrian personal cost image 65 Figure 4 23 (a) Detect pedestrian, (b) Lost tracking 66 Figure 4 24 Concept of mean shift 67 Figure 4 25 Feature of mean shift tracking 69 Figure 4 26 Bhattacharyya coefficient 70 Figure 4 27 The result of tracking 71 Figure 5 1 Graphic user interface 73 Figure 5 2 (a) Skeletal viewer, (b) Skeleton positions relative to the human body [45] 74 Figure 5 3 Photos of hardware: (a) The robot, Bunny, (b) Webcam [28], (c) SICK LMS-291 [21] 75 Figure 5 4 Kinect [43] 75 Figure 5 5 One queue line 76 Figure 5 6 General case experiment of goal weighting 77 Figure 5 7 Tragedy of goal weighting, (a~c) Meaningless result, (d~f) Converge on the wrong way 78 Figure 5 8 Result of the addition term of goal weighting 79 Figure 5 9 Simulation of queue length prediction, (a) Result of insufficient observation time, (b) Result of the time after 3 seconds 81 Figure 5 10 Simulation animation, (a) Two lines with same length, (b) Two lines with different length 83 Figure 5 11 Experiment of two queues 84 Figure 5 12 Experiment of three lines 8613495005 bytesapplication/pdf論文公開時間：2016/01/27論文使用權限：同意有償授權(權利金給回饋本人)排隊虛擬試穿系統排隊檢測動態環境航行社會行為預測追蹤thesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/263163/1/ntu-102-R00522806-1.pdf