VIETNAM NATIONAL UNIVERISTY - HO CHI MINH CITY HO CHI MINH CITY UNIVERSITY OF TECHNOLOGY (HCMUT) FACULTY OF COMPUTER SCIENCE & TECHNOLOGY G RADUATION T HESIS A N AVIGATION S OLUTION WITH 3D M ODELS M AJOR : COMPUTER ENGINEERING Superviosrs: Assoc. Pham Quoc Cuong - HCMUT Assoc. Phan Thanh An - HCMUT Reviewer: Assoc. Tran Van Hoai - HCMUT Authors: Nguyen Dinh Minh - 1952092 Luu Trinh Lam - 1952315 Committee: COMPUTER ENGINEERING OISP 2 HO CHI MINH CITY - June-2023 ĐẠI HỌC QUỐC GIA TP.HCM CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƯỜNG ĐẠI HỌC BÁCH KHOA Độc lập - Tự do - Hạnh phúc KHOA:KH & KT Máy tính ____ NHIỆM VỤ LUẬN ÁN TỐT NGHIỆP BỘ MÔN:KHMT ____________ Chú ý: Sinh viên phải dán tờ này vào trang nhất của bản thuyết trình HỌ VÀ TÊN: - Lưu Trịnh Lâm 1952315 Computer Engineering - Nguyễn Đình Minh 1952092 Computer Engineering NGÀNH: Kỹ thuật Máy tính ___________________ LỚP: MT19CLC ____________ 1.
Đầu đề luận án: A Navigation Solution with 3D Model 2. Nhiệm vụ (yêu cầu về nội dung và số liệu ban đầu): - Conduct a thorough survey on the topic of 3D navigation - Propose a solution for the HCMUT’s main campus - Implement the proposed solution with a particular programming language - Deploy the system with a mobile platform - Evaluate the system 3. Ngày giao nhiệm vụ luận án: 10/01/2023 4. Ngày hoàn thành nhiệm vụ: 01/6/2023 5.
Họ tên giảng viên hướng dẫn: Phần hướng dẫn: 1) PGS. Phạm Quốc Cường _______________________________________________ 2) __________________________________________________________________________ 3) __________________________________________________________________________ Nội dung và yêu cầu LVTN đã được thông qua Bộ môn. Ngày 10 tháng 01 năm 2022 CHỦ NHIỆM BỘ MÔN GIẢNG VIÊN HƯỚNG DẪN CHÍNH (Ký và ghi rõ họ tên) (Ký và ghi rõ họ tên) Phạm Quốc Cường Phạm Quốc Cường PHẦN DÀNH CHO KHOA, BỘ MÔN: Người duyệt (chấm sơ bộ): _______________________ Đơn vị: _______________________________________ Ngày bảo vệ: __________________________________ Điểm tổng kết: _________________________________ Nơi lưu trữ luận án: _____________________________ iii TRVONG BAI HOC BACH KHOA C<)NG HOA XA H<)I CHU NGHiA VI~T NAM KHOA KH & KT MAY TINH D(k I~p - T1,1· do - H~nh phuc Ngay 12 thang 6 nam 2023 PHIEU DANH GIA LU~N VAN/ DO AN TOT NGHI~P (Danh cha nguo·i hu6ng dd19/phan bi?n) 6. H9 va ten SV: LU'u Trinh Lam 1952315 Computer Engineering Nguyen Dlnh Minh 1952092 Computer Engineering 2.
D6 tai: A Navigation Solution with 30 Model 3. H9 ten nguai hu6ng d~n/phan bi9n: Ph9m Quoc CU'ang 4. T6ng quat v6 ban thuy~t minh: s6 trang: s6 chuang: s6 bang s6 li~u s6 hinh ve: s6 tai li~u tham khao: Ph~n m6m tinh toan: Hi~n v~t (san ph~m) 5. Nhfrng uu di~m chinh ctia L VI DA TN: - Students fulfill the basic requirements of the capstone project when the proposed and implemented system can navigate position of a perdestrian.
- Experimental results are acceptable. - The report is well-written. - Students have conducted the capstone project in a scientific approach. Nhfrng thi~u sot chinh cua LV/DATN: - The system should be tested in a real environment.
- A comparison with others should be conducted. - Details of measurement errors should be reported. D6 nghi: Duqc bao v~ [8] B6 sung them d~ bao v~ o Khong duqc bao v~ o 8. Cac cau hoi SV phai tra lai tru6c H(li d6ng: 9.
Danh gia chung (b~ng chfr: Xwit s~c, Gioi, Kha, TB): Di~m: 9.8/10 Ky ten (ghi ro hQ ten) Ph~m Qu6c Cuong v • ~if)2 (LC ICT/"l T TRUONG D~I HQC BACH KHOA CONG HOA XA HQI CHU NGHIA VIET NAM KHOA KH & KT MAY TiNH D<)c l~p - Tµ do - Hi;mh phuc Ngay 2 thang 6 nam 2023. VAN/ DO AN TOT NGHIEP PHIEU DANH GIA LUAN. HQ va ten SV: Nguy~n Dinh Minh MSSV: 1952092 Nganh (chuyen nganh): CE HQ va ten SV : Luu Trinh Lam MSSV: 1952315 Nganh (chuyen nganh): CE 2. D~ tai: A navigation solution with 3D models 3.
HQ ten nguai phan bi~n: Trfrn Van Hoai 4. T6ng quat v~ ban thuy~t minh: s6 trang: 94 s6 chuang: 6 s6 bang s6 li~u: 8 s6 hinh ve: 18 s6 tai li~u tham khao : 75 Phfrn m~m tinh toan: I Hi~n v~t (san phftm) 5. Nhfrng uu diSm chinh cua LV/ DATN: - The students proposed SCL algorithm to locate the position in a no-GPS environment. The algorithm has a low complexity (polynomial).
The idea of the algorithm is novel, worthy to exploit further to have a good study. - Experiments in HCMUT map show the SCL can be helpful in a well-controlled environment. In the thesis, it is assumed that distances from a foothold to neighboring corners and angles between them are measurable (by ce1iain techniques which are not mentioned in the thesis). - A set of other algorithms for path planning (triangulation, channel search, funnel, path refinement,.
) have been implemented to show a system of navigation in 2D. Nhfrng thi~u s6t chinh cua LV/DATN: - There is no 3D models in the thesis, although the students' contribution is high. - The dataset (HCMUT map) is not enough to test the proposed algorithms and implementations. The number of points (corners) in the experiments is too small to be applied in practice.
- "congruent" in mathematics means same shape or size. It does not match exactly with the concepts (SCL) in the thesis. - The thesis does not describe the cases of failures which are possibly characterized.D~ nghi: Duqc bao v~ ~ B6 sung them dS bao v~ D Khong duqc bao v~ D 8. Cac cau h6i SV phai tra lai tru&c H<)i d6ng : a.
Can student formulate SWAP in adaptive structure ansatz more mathematically? 9. Danh gia chung (b~ng chfr: Xu~t sic, Gi6i, Kha, TB): Gi6i DiSm: 9110 Ky ten (ghi ro hQ ten) vii D ECLARATION OF AUTHORSHIP I, Minh Nguyen, together with my colleague, Lam Luu, declare that this project, titled A Navigation Solution with 3D Models, and the work presented in it are my own. I confirm that: • This work was done wholly or mainly while in candidature for a research degree at HCMUT. • Where any part of this project has previously been submitted for a degree or any other qualification at HCMUT or any other institution, this has been clearly stated.
• Where I have consulted the published work of others, this is always clearly attributed. • Where I have quoted from the work of others, the source is always given. With the exception of such quotations, this project is entirely my own work. • I have acknowledged all main sources of help.
• Where the project is based on work done by myself jointly with others, I have made clear exactly what was done by others and what I have con- tributed myself. Signed: Date: July 5th, 2023 ix This thesis is dedicated to Ho Chi Minh City University of Technology. A CKNOWLEDGMENT First of all, this work would not have existed if it had not been for the belief our instructors gave us when we decided on the topic of our capstone project. We want to express our gratitude to the benevolent supervisor, the wholesome professor, and the dedicated teacher - Dr.
Pham Quoc Cuong, for granting us the wish to research, design, and implement the project when even we our- selves were skeptical about its success. Secondly, we would like to express our heartfelt appreciation and gratitude to Dr. Phan Thanh An for his exceptional guidance and unwavering support throughout the entire process of the algo- rithm consultancy. His profound expertise and unwavering commitment to excellence have played an integral role in shaping the success of this project.
Thirdly, we appreciate the insightful feedback from Associate Prof. Tran Van Hoai, who pinpointed major issues throughout the thesis. Finally, we express acknowledgment to our university for providing such a stable and cooperative working environment to support the development of research projects. The project also received support from various sources.
We would like to give special credit to the group of remarkable students at the Ho Chi Minh City University of Architecture for providing the map of some districts in Ho Chi Minh City. They are the Lee Kuan Yew Centre for Innovative Cities, SUTD. This map plays a crucial role in evaluating the method proposed in the work. All and all, we appreciate the related parties for publishing the knowledge involved in developing this project.
xiii A BSTRACT The thesis focuses on indoor navigation solutions, addressing ongoing discus- sions and advancements in the field. Previous works have explored localization methods using advanced sensors in smartphones, enabling real-time predic- tion of pedestrians’ spatial location. However, these methods face limitations in environments where infrastructure is temporarily shut down. To overcome this challenge, the thesis proposes a complementary localization method called Statically Congruent Localization, which supplements other localization tech- nologies.
Additionally, a path-planning implementation in navigation meshes is presented to enhance the solution’s effectiveness. To demonstrate practi- cality and versatility, a multiplatform application is developed, integrating the static localization method, path planning algorithm, and result visualization into a fusion platform. Experimental evaluations are conducted on the new localization method and the path-planning usage. The localization method performs well on typ- ical maps but encounters challenges with large datasets.
The path-planning implementation reveals insights into the behavior of the heuristic model and refinement radius selection. Notably, the plain Euclidean and Manhattan dis- tance costs, commonly used in grid-based solutions, contribute only about 66% to the heuristic search success. For refinement radius, a value below 2.0 is rec- ommended for a 1:10 scale map. The experiment also explores the impact of premature termination in the Dijkstra search on the resulting optimal path.
xv C ONTENTS Declaration of Authorship ix Acknowledgment xiii Abstract xv List of Figures xix List of Tables xxi 1 Introduction 1 1.1 Indoor Localization and Navigation. 8 2 Background and Related Work 9 2.1 Global Positioning System .4 Magnetic-based Localization .5 Sound-based Localization .6 Visual-based Localization .1 Path Planning Algorithm .2 Relative Distance and Angle Inference .1 Statically Congruent Localization. 37 xvii xviii C ONTENTS 3.3 Refinement Method for A Line String Path .2 Computing Tangent Anchors .1 Uniform Map Data .2 Polygon-wise Structures .3 Path Planning Implementation .3 Path from Channel .3 Path Planning Experiments. 85 6 Conclusion and Future Work 87 Bibliography 91 L IST OF F IGURES 1.1 Ho Chi Minh City University of Technology Campus [27] .3 Channel search with Dijkstra produces a globally optimal path that might be expensive on large maps (Left).
Channel search with heuristic efficiently produces an acceptable path but might be subject to dead-ends (Right).4 Heuristic search encounters dead-end when the oriented walk tran- sitions to a triangle whose vertices belong to the same obstacle.5 Minimum path inside channel without refinement (Left). Mini- mum path inside channel with refinement (Right).1 The three layers of clean architecture .2 Abstract block design of the system .1 An Input Map. Ho Chi Minh City University of Technology cam- pus (Left) and The detected corners are shown in red dots (Right).1 Plain Map for The Simulator .2 OpenJUMP Polygon Modeling .3 Heuristic Search Failed Attempts .5 Flaw-Refined Paths .6 Flaw-Refined Paths with Dijkstra only .7 Native Android application built with Compose. 85 xix L IST OF TABLES 2.1 Summary of WiFi-based Localization Methods .2 Comparison of Dijkstra search and Heuristic search .1 Experiment on both phases in Ho Chi Minh center: altering map size .2 Experiment on Online Phase in Ho Chi Minh center: altering num- ber of visible points .3 Adding some noise .4 Exhaustive Test on the HCMUT Campus Map .5 Selective Test on Heuristic Weights.
Heuristic failure is measured with different weights distributed to the Euclidean distance cost and Manhattan distance cost.6 Selective Test on Refinement Radius .7 Selective Test on Refinement Radius.
