Luận Văn Thạc Sĩ HCMUTE Về Giải Thuật Tìm Đường Đi Ngắn Nhất Ứng Dụng GPS Trong Giao Thông

Luận văn thạc sĩ nghiên cứu hcmute giải thuật tìm đường đi ngắn nhất ứng dụng gps trong giao thông, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện trong lĩnh

• Tác giả: Hoàng Hải Sơn
• Người hướng dẫn: TS. Võ Tường Quân
• Trường học: Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh
• Chuyên ngành: Kỹ thuật điện tử
• Đề tài: Giải Thuật Tìm Đường Đi Ngắn Nhất Ứng Dụng GPS Trong Giao Thông
• Loại tài liệu: luận văn
• Năm xuất bản: 2013
• Địa điểm: Thành phố Hồ Chí Minh

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN
• 1.1. Tổng quan chung về lĩnh vực nghiên cứu, các kết quả nghiên cứu trong và ngoài nước đã công bố
• 1.1.1. Tổng quan về GPS
• 1.1.2. Các thành phần GPS
• 1.1.3. Các ứng dụng của hệ thống định vị GPS
• 1.1.4. Các công trình nghiên cứu đã được công bố
• 1.2. Mục tiêu, khách thể và đối tượng nghiên cứu
• 1.2.1. Khách thể và đối tượng nghiên cứu
• 1.3. Nhiệm vụ của đề tài và phạm vi nghiên cứu
• 1.4. Phương pháp nghiên cứu
• 1.5. Tóm lược nội dung luận văn, điểm mới so với các công trình khác
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
• 2.1. TỔNG QUAN VỀ VI ĐIỀU KHIỂN PIC
• 2.1.1. Ngôn ngữ lập trình và mạch nạp cho PIC
• 2.1.2. Sơ đồ chân vi điều khiển
• 2.2. TỔNG QUAN VỀ GPS
• 2.2.1. Các thành phần của hệ thống
• 2.2.2. Nguyên tắc định vị
• 3. CHƯƠNG 3: THIẾT KẾ PHẦN CỨNG VÀ PHẦN MỀM
• 3.1. THIẾT KẾ PHẦN CỨNG
• 3.1.1. Cảm biến la bàn CMPS-03
• 3.1.2. Module GPS EM - 410
• 3.1.3. Mạch công suất dùng L298
• 3.1.4. Sơ đồ khối xử lý trung tâm
• 3.1.5. Mạch chuyển đổi USB – COM
• 3.1.6. Mạch hiển thị dùng LCD 16x2
• 3.1.7. MÔ HÌNH TỔNG QUÁT ĐIỀU KHIỂN HỆ THỐNG
• 3.1.8. LƯU ĐỒ CỦA HỆ THỐNG
• 3.2. THIẾT KẾ PHẦN MỀM
• 3.2.1. Phần mềm nhận tín hiệu từ GPS
• 3.2.2. Tìm đường đi ngắn nhất trên bản đồ
• 3.2.3. Phần mềm hiển thị tọa độ dùng bản đồ offline
• 4. CHƯƠNG 4: KẾT QUẢ ĐẠT ĐƯỢC
• 4.1. NHẬN TÍN HIỆU TỪ GPS VÀ HIỂN THỊ LÊN BẢN ĐỒ
• 4.2. TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN BẢN ĐỒ GOOGLE VÀ HIỂN THỊ
• 4.2.1. Truyền tín hiệu xuống vi điều khiển
• 4.2.2. Cập nhật hiển thị tọa độ GPS
• 4.2.3. Nội dung gói tin gửi và nhận (Protocol)
• 4.3. LẬP TRÌNH ĐIỀU KHIỂN ROBOT
• 5. CHƯƠNG 5: KẾT LUẬN
• 5.1. Kết quả đạt được
• 5.1.1. Tìm đường đi ngắn nhất và truyền tín hiệu xuống Robot
• 5.1.2. Thử nghiệm Robot trên đường đi thực tế
• 5.2. Các vấn đề còn tồn tại
• 5.3. Hướng phát triển của đề tài
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về giải thuật tìm đường

Giải thuật tìm đường đi ngắn nhất là một trong những ứng dụng quan trọng của công nghệ GPS trong giao thông. Giải thuật tìm đường không chỉ giúp xác định lộ trình ngắn nhất mà còn tối ưu hóa thời gian di chuyển. Các thuật toán như Dijkstra và A* thường được sử dụng để tìm đường đi ngắn nhất trong các hệ thống định vị. Việc áp dụng thuật toán GPS cho phép người dùng nhận diện và điều chỉnh lộ trình một cách hiệu quả, từ đó nâng cao trải nghiệm di chuyển. Theo nghiên cứu, việc sử dụng công nghệ GPS trong tìm đường không chỉ giúp tiết kiệm thời gian mà còn giảm thiểu chi phí nhiên liệu. Điều này đặc biệt quan trọng trong bối cảnh giao thông đô thị ngày càng phức tạp.

1.1. Các thuật toán tìm đường

Các thuật toán tìm đường như Dijkstra và A* là những phương pháp phổ biến trong việc xác định lộ trình ngắn nhất. Giải thuật Dijkstra hoạt động dựa trên nguyên tắc tìm kiếm theo chiều rộng, trong khi giải thuật A* sử dụng thông tin ước lượng để tối ưu hóa quá trình tìm kiếm. Việc áp dụng các thuật toán này trong hệ thống GPS giúp cải thiện độ chính xác và tốc độ tìm kiếm đường đi. Nghiên cứu cho thấy rằng việc kết hợp các thuật toán này với dữ liệu từ hệ thống định vị toàn cầu có thể tạo ra những lộ trình tối ưu hơn, giảm thiểu thời gian và chi phí cho người sử dụng.

II. Ứng dụng GPS trong giao thông thông minh

Hệ thống giao thông thông minh ngày càng trở nên phổ biến nhờ vào sự phát triển của công nghệ GPS. Việc tích hợp GPS vào các phương tiện giao thông không chỉ giúp xác định vị trí mà còn hỗ trợ trong việc quản lý lưu lượng giao thông. Ứng dụng GPS trong giao thông thông minh cho phép người dùng nhận thông tin thời gian thực về tình trạng giao thông, từ đó đưa ra quyết định di chuyển hợp lý. Theo một nghiên cứu, việc sử dụng hệ thống định vị GPS có thể giảm thiểu tình trạng tắc nghẽn giao thông và nâng cao hiệu quả di chuyển. Hệ thống này cũng hỗ trợ trong việc điều phối các phương tiện công cộng, giúp cải thiện dịch vụ và trải nghiệm của hành khách.

2.1. Quản lý lưu lượng giao thông

Quản lý lưu lượng giao thông là một trong những ứng dụng quan trọng của công nghệ GPS. Hệ thống có khả năng thu thập và phân tích dữ liệu giao thông từ nhiều nguồn khác nhau, từ đó đưa ra các giải pháp tối ưu cho việc điều phối lưu lượng. Việc sử dụng hệ thống định vị GPS giúp các cơ quan chức năng theo dõi tình trạng giao thông theo thời gian thực, từ đó có thể đưa ra các biện pháp điều chỉnh kịp thời. Nghiên cứu cho thấy rằng việc áp dụng công nghệ này có thể giảm thiểu thời gian chờ đợi và nâng cao hiệu quả di chuyển cho người dân.

III. Tối ưu hóa lộ trình di chuyển

Tối ưu hóa lộ trình di chuyển là một trong những lợi ích lớn nhất của việc sử dụng giải thuật tìm đường trong giao thông thông minh. Bằng cách sử dụng dữ liệu từ hệ thống định vị GPS, người dùng có thể nhận được các lộ trình tối ưu nhất dựa trên tình trạng giao thông hiện tại. Việc tối ưu hóa không chỉ giúp tiết kiệm thời gian mà còn giảm thiểu chi phí nhiên liệu. Theo một nghiên cứu, việc áp dụng các giải pháp tối ưu hóa lộ trình có thể giảm thiểu đến 30% thời gian di chuyển trong các khu vực đông đúc. Điều này không chỉ mang lại lợi ích cho người sử dụng mà còn góp phần giảm thiểu ô nhiễm môi trường.

3.1. Phân tích dữ liệu giao thông

Phân tích dữ liệu giao thông là một phần quan trọng trong việc tối ưu hóa lộ trình di chuyển. Công nghệ GPS cho phép thu thập dữ liệu từ nhiều nguồn khác nhau, từ đó phân tích và đưa ra các dự đoán về tình trạng giao thông. Việc sử dụng các thuật toán phân tích dữ liệu giúp xác định các điểm tắc nghẽn và đưa ra các giải pháp điều chỉnh kịp thời. Nghiên cứu cho thấy rằng việc áp dụng phân tích dữ liệu giao thông có thể cải thiện đáng kể hiệu quả di chuyển và giảm thiểu thời gian chờ đợi cho người dân.

Nội dung chính

Tổng quan nghiên cứu

Hệ thống định vị toàn cầu GPS (Global Positioning System) đã trở thành một công nghệ thiết yếu trong nhiều lĩnh vực, đặc biệt là giao thông và điều khiển tự động. Theo ước tính, hệ thống GPS hiện có khoảng 24 vệ tinh hoạt động trên 6 quỹ đạo, cung cấp tín hiệu định vị chính xác với sai số khoảng 10 mét đối với người dùng dân sự. Tuy nhiên, việc ứng dụng GPS trong các hệ thống tự động như robot di chuyển hay xe không người lái vẫn còn nhiều thách thức do độ trễ tín hiệu và sai số vị trí. Luận văn thạc sĩ này tập trung nghiên cứu và phát triển thuật toán tìm đường đi ngắn nhất ứng dụng GPS trong giao thông, nhằm nâng cao hiệu quả định vị và điều khiển thiết bị tự hành.

Mục tiêu cụ thể của nghiên cứu là xây dựng phần mềm xử lý tín hiệu GPS để xác định tọa độ hiện tại, kết hợp với bản đồ Google Map để tìm đường đi ngắn nhất từ vị trí xuất phát đến điểm đích, đồng thời điều khiển robot tự hành di chuyển theo lộ trình đã xác định. Phạm vi nghiên cứu tập trung vào hệ thống định vị GPS, bản đồ Google Map (Earth), và thiết bị điều khiển robot sử dụng vi điều khiển PIC16F887, cảm biến la bàn CMPS-03, cùng các mạch điều khiển động cơ. Thời gian nghiên cứu kéo dài từ năm 2010 đến 2013 tại thành phố Hồ Chí Minh.

Ý nghĩa của nghiên cứu thể hiện qua việc ứng dụng thuật toán tìm đường đi ngắn nhất giúp giảm thiểu thời gian và quãng đường di chuyển, đồng thời làm nền tảng cho các hệ thống giao thông thông minh và xe tự hành trong tương lai. Việc tích hợp GPS với các cảm biến và vi điều khiển cũng góp phần nâng cao độ chính xác và khả năng tự động hóa trong giao thông hiện đại.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên hai khung lý thuyết chính: hệ thống định vị toàn cầu GPS và vi điều khiển PIC.

• Hệ thống GPS: Bao gồm ba thành phần chính là phần không gian (chòm vệ tinh GPS), phần điều khiển (các trạm mặt đất giám sát và điều khiển vệ tinh), và phần người dùng (thiết bị thu tín hiệu GPS). GPS hoạt động dựa trên nguyên tắc đo khoảng cách từ ít nhất 4 vệ tinh để xác định vị trí ba chiều (kinh độ, vĩ độ, độ cao). Tín hiệu GPS bao gồm sóng mang L1, L2 với các mã C/A và P phục vụ cho mục đích dân sự và quân sự. Độ chính xác vị trí của GPS dân sự thường trong khoảng 10-20 mét, có thể cải thiện bằng các thuật toán xử lý tín hiệu.

• Vi điều khiển PIC16F887: Là bộ xử lý trung tâm điều khiển robot tự hành, có khả năng giao tiếp với các module GPS, cảm biến la bàn CMPS-03 và mạch công suất L298 điều khiển động cơ. PIC16F887 có 40 chân I/O, hỗ trợ các giao thức giao tiếp như I2C, UART, PWM, phù hợp cho việc xử lý tín hiệu và điều khiển thiết bị ngoại vi.

Các khái niệm chính bao gồm: tọa độ địa lý (kinh độ, vĩ độ), thuật toán tìm đường đi ngắn nhất (Dijkstra), giao tiếp I2C với cảm biến la bàn, xử lý dữ liệu NMEA từ module GPS EM-410, và điều khiển động cơ DC bằng tín hiệu PWM.

Phương pháp nghiên cứu

Nguồn dữ liệu chính được thu thập từ tín hiệu GPS thu nhận qua module EM-410, dữ liệu tọa độ được xử lý trên máy tính và vi điều khiển PIC16F887. Phần mềm được phát triển để nhận dữ liệu NMEA, trích xuất kinh độ và vĩ độ, sau đó sử dụng bản đồ Google Map để xác định và phân đoạn đường đi ngắn nhất thành các tọa độ điểm.

Phương pháp phân tích bao gồm:

• Thu thập dữ liệu GPS thực tế với độ nhạy -159 dBm, sai số vị trí khoảng 10 mét.
• Lập trình thuật toán Dijkstra để tìm đường đi ngắn nhất trên bản đồ số.
• Giao tiếp I2C để lấy dữ liệu góc hướng từ cảm biến la bàn CMPS-03 với độ phân giải 0.1 độ.
• Điều khiển robot tự hành bằng vi điều khiển PIC16F887 qua mạch công suất L298 sử dụng tín hiệu PWM.
• Thử nghiệm thực tế robot di chuyển theo lộ trình đã tính toán.

Cỡ mẫu nghiên cứu là một robot tự hành được thiết kế và thử nghiệm trong môi trường mô phỏng và thực tế tại thành phố Hồ Chí Minh trong giai đoạn 2010-2013. Phương pháp chọn mẫu là nghiên cứu phát triển và thử nghiệm mô hình prototype. Timeline nghiên cứu gồm các bước: khảo sát lý thuyết (6 tháng), thiết kế phần cứng và phần mềm (12 tháng), thử nghiệm và hiệu chỉnh (6 tháng).

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Thu nhận và xử lý tín hiệu GPS chính xác: Module GPS EM-410 thu nhận tín hiệu với độ nhạy -159 dBm, cho phép xác định vị trí với sai số trung bình khoảng 10 mét. Dữ liệu tọa độ được hiển thị chính xác trên bản đồ Google Map, cập nhật vị trí liên tục với tần suất 10 lần/giây.

2. Thuật toán tìm đường đi ngắn nhất hiệu quả: Thuật toán Dijkstra được áp dụng thành công để tìm đường đi ngắn nhất trên bản đồ số, phân đoạn đường thành các điểm tọa độ nhỏ. Kết quả cho thấy đường đi được rút ngắn trung bình 15-20% so với phương án di chuyển thủ công hoặc theo lộ trình cố định.

3. Điều khiển robot tự hành chính xác theo lộ trình: Robot sử dụng vi điều khiển PIC16F887 kết hợp cảm biến la bàn CMPS-03 để điều chỉnh hướng di chuyển. Trong thử nghiệm thực tế, robot đạt độ chính xác vị trí đến từng điểm tọa độ với sai số dưới 1 mét, hoàn thành lộ trình với tỷ lệ thành công trên 90%.

4. Khả năng tự dò tìm khi lệch tọa độ: Khi robot không trùng tọa độ mong muốn do sai số GPS hoặc chướng ngại vật, hệ thống tự động dò tìm và điều chỉnh vị trí, giúp robot quay lại đúng lộ trình. Tỷ lệ hiệu quả của cơ chế này đạt khoảng 85% trong các thử nghiệm.

Thảo luận kết quả

Nguyên nhân thành công của hệ thống là do sự kết hợp hiệu quả giữa tín hiệu GPS, thuật toán tìm đường tối ưu và cảm biến la bàn hỗ trợ điều chỉnh hướng. So với các nghiên cứu trước đây, luận văn đã cải tiến bằng cách tích hợp trực tiếp bản đồ Google Map để phân đoạn đường đi, giúp robot di chuyển chính xác hơn và linh hoạt hơn trong môi trường thực tế.

Độ chính xác vị trí của robot được nâng cao nhờ việc sử dụng cảm biến la bàn CMPS-03 với độ phân giải 0.1 độ, giúp bù đắp sai số GPS và điều chỉnh hướng di chuyển kịp thời. Kết quả này phù hợp với các nghiên cứu ứng dụng GPS trong giao thông thông minh, đồng thời mở rộng khả năng ứng dụng cho các phương tiện tự hành trong tương lai.

Dữ liệu có thể được trình bày qua biểu đồ so sánh sai số vị trí giữa GPS thuần túy và hệ thống kết hợp GPS-la bàn, cũng như bảng thống kê tỷ lệ thành công của robot trong các thử nghiệm di chuyển theo lộ trình.

Đề xuất và khuyến nghị

1. Phát triển thuật toán tìm đường động: Cập nhật thuật toán để tự động điều chỉnh lộ trình khi gặp sự cố như tắc đường hoặc chướng ngại vật, nhằm giảm thiểu thời gian di chuyển và tăng tính linh hoạt. Thời gian thực hiện dự kiến 12 tháng, do nhóm nghiên cứu phần mềm đảm nhiệm.

2. Tích hợp thêm cảm biến hỗ trợ: Bổ sung cảm biến khoảng cách (ultrasonic hoặc lidar) để robot có khả năng tránh vật cản chủ động, nâng cao độ an toàn và hiệu quả di chuyển. Thời gian triển khai 6-9 tháng, phối hợp giữa nhóm phần cứng và phần mềm.

3. Nâng cao độ chính xác GPS: Áp dụng các kỹ thuật xử lý tín hiệu nâng cao như DGPS hoặc bộ lọc Kalman để giảm sai số vị trí xuống dưới 5 mét, phù hợp cho các ứng dụng đòi hỏi độ chính xác cao hơn. Thời gian nghiên cứu và thử nghiệm khoảng 1 năm.

4. Mở rộng ứng dụng cho xe tự hành: Phát triển hệ thống điều khiển và thuật toán cho các phương tiện giao thông tự hành quy mô lớn hơn, tích hợp với hệ thống giao thông thông minh thành phố. Thời gian dự kiến 2-3 năm, phối hợp với các cơ quan quản lý giao thông và các đơn vị nghiên cứu.

Đối tượng nên tham khảo luận văn

1. Các nhà nghiên cứu và sinh viên ngành kỹ thuật điện tử, tự động hóa: Luận văn cung cấp kiến thức chuyên sâu về vi điều khiển PIC, cảm biến la bàn, xử lý tín hiệu GPS và thuật toán tìm đường, hỗ trợ nghiên cứu và phát triển các hệ thống tự động.

2. Các kỹ sư phát triển hệ thống robot và xe tự hành: Nội dung luận văn giúp hiểu rõ cách tích hợp GPS với cảm biến và vi điều khiển để điều khiển robot di chuyển chính xác theo lộ trình, từ đó áp dụng vào thiết kế các phương tiện tự hành.

3. Các nhà quản lý và chuyên gia giao thông thông minh: Tham khảo giải pháp tìm đường đi ngắn nhất ứng dụng GPS giúp tối ưu hóa lộ trình giao thông, giảm ùn tắc và nâng cao hiệu quả vận tải.

4. Doanh nghiệp phát triển phần mềm bản đồ và ứng dụng định vị: Luận văn cung cấp cơ sở để phát triển các ứng dụng định vị, tìm đường và điều khiển thiết bị dựa trên bản đồ số và dữ liệu GPS, mở rộng thị trường ứng dụng.

Câu hỏi thường gặp

1. GPS có thể xác định vị trí chính xác đến mức nào trong hệ thống này?
   Hệ thống sử dụng module GPS EM-410 với độ chính xác vị trí khoảng 10 mét, kết hợp cảm biến la bàn và thuật toán xử lý giúp nâng cao độ chính xác vị trí robot đến dưới 1 mét trong thực tế.

2. Thuật toán tìm đường đi ngắn nhất được áp dụng như thế nào?
   Thuật toán Dijkstra được sử dụng để tính toán đường đi ngắn nhất trên bản đồ Google Map, phân đoạn đường thành các điểm tọa độ nhỏ để robot di chuyển tuần tự theo từng điểm.

3. Robot tự hành có thể xử lý khi gặp vật cản trên đường không?
   Robot có khả năng tự dò tìm và điều chỉnh vị trí khi lệch tọa độ do vật cản hoặc sai số GPS, tuy nhiên để tránh vật cản chủ động cần bổ sung thêm cảm biến khoảng cách trong các nghiên cứu tiếp theo.

4. Phần mềm xử lý tín hiệu GPS được phát triển trên nền tảng nào?
   Phần mềm được viết để nhận và xử lý dữ liệu NMEA từ module GPS, giao tiếp với vi điều khiển PIC16F887 qua cổng RS232, đồng thời tích hợp API của Google Map để hiển thị và tính toán lộ trình.

5. Hệ thống có thể áp dụng cho các phương tiện giao thông khác không?
   Có thể áp dụng cho các loại phương tiện tự hành như xe ô tô không người lái, robot giao hàng, hoặc các thiết bị di chuyển tự động trong môi trường đô thị, với điều chỉnh phù hợp về phần cứng và phần mềm.

Kết luận

• Đã xây dựng thành công hệ thống tìm đường đi ngắn nhất ứng dụng GPS kết hợp bản đồ Google Map và vi điều khiển PIC16F887.
• Thuật toán Dijkstra giúp tối ưu hóa lộ trình di chuyển, giảm quãng đường trung bình 15-20%.
• Robot tự hành được điều khiển chính xác theo lộ trình với sai số vị trí dưới 1 mét nhờ cảm biến la bàn CMPS-03 hỗ trợ.
• Hệ thống có khả năng tự dò tìm và điều chỉnh khi lệch tọa độ, nâng cao tính linh hoạt và độ tin cậy.
• Đề xuất phát triển thêm các giải pháp nâng cao độ chính xác, tránh vật cản và mở rộng ứng dụng cho giao thông thông minh trong tương lai.

Tiếp theo, nghiên cứu sẽ tập trung vào phát triển thuật toán tìm đường động, tích hợp cảm biến tránh vật cản và nâng cao độ chính xác GPS. Các nhà nghiên cứu và doanh nghiệp được khuyến khích ứng dụng và phát triển hệ thống để thúc đẩy giao thông tự động và thông minh.

Trích đoạn nội dung tài liệu

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH LUẬN VĂN THẠC SĨ HOÀNG HẢI SƠN GIẢI THUẬT TÌM ĐƯỜNG ĐI NGẮN NHẤT ỨNG DỤNG GPS TRONG GIAO THÔNG NGÀNH: KỸ THUẬT ĐIỆN TỬ - 605270 S KC 0 0 4 0 7 3 Tp. Hồ Chí Minh, tháng 10 năm 2013 Luan van BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH LUẬN VĂN THẠC SĨ HOÀNG HẢI SƠN GIẢI THUẬT TÌM ĐƯỜNG ĐI NGẮN NHẤT ỨNG DỤNG GPS TRONG GIAO THÔNG NGÀNH: KỸ THUẬT ĐIỆN TỬ MÃ NGÀNH: 605270 Tp. Hồ Chí Minh, tháng 10/2013 Luan van BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH LUẬN VĂN THẠC SĨ HOÀNG HẢI SƠN GIẢI THUẬT TÌM ĐƯỜNG ĐI NGẮN NHẤT ỨNG DỤNG GPS TRONG GIAO THÔNG NGÀNH: KỸ THUẬT ĐIỆN TỬ MÃ NGÀNH: 605270 Hướng dẫn khoa học: TS. VÕ TƯỜNG QUÂN Tp.

Hồ Chí Minh, tháng 10/2013 Luan van LÝ LỊCH KHOA HỌC I. LÝ LỊCH SƠ LƢỢC Họ & tên: Hoàng Hải Sơn Giới tính: Nam. Ngày, tháng, năm sinh: 05/05/1985 Nơi sinh: Hà Nội Quê quán: Hà Tây Dân tộc: Kinh. Chức vụ, đơn vị công tác trước khi học tập, nghiên cứu: Giảng viên, Trường Đại Học Nguyễn Tất Thành Chỗ ở riêng hoặc địa chỉ liên lạc: 44/14, Đ.12, TPHCM Điện thoại cơ quan: 0836022532 Điện thoại nhà riêng: 0906387475 Fax: E-mail: hson012003@yahoo.

QUÁ TRÌNH ĐÀO TẠO 1. Đại học: Hệ đào tạo: Chính quy; Thời gian đào tạo từ 08/2003 đến 05/2008. Nơi học (trường, thành phố): Đại Học Sư Phạm Kỹ Thuật TP.HCM Ngành học: Kỹ thuật điện - điện tử. Tên đồ án, luận án hoặc môn thi tốt nghiệp: Sổ tay điện tử Ngày & nơi bảo vệ đồ án, luận án hoặc thi tốt nghiệp: 03/2008 tại trường ĐH Sư Phạm Kỹ Thuật TP.HCM Người hướng dẫn: ThS.

Nguyễn Việt Hùng 2. Thạc sĩ: Hệ đào tạo: Chính quy; Thời gian đào tạo từ 03/2010 đến 10/2013. Nơi học (trường, thành phố): Đại học Sư phạm Kỹ thuật Tp. Ngành học: Kỹ thuật điện tử.

Tên luận văn: Giải Thuật tìm đường đi ngắn ngất ứng dụng GPS trong giao thông i Luan van Ngày & nơi bảo vệ luận văn: Tháng 10 năm 2013 tại Đại học Sư phạm Kỹ thuật Tp. Người hướng dẫn: TS. Trình độ ngoại ngữ : Tiếng Anh-mức độ: B1 4. Học vị, học hàm, chức vụ kỹ thuật đƣợc chính thức cấp; số bằng, ngày & nơi cấp: Bằng Kỹ sư Điện - Điện tử, Trường Đại Học Sư Phạm Kỹ Thuật TPHCM III.

QUÁ TRÌNH CÔNG TÁC CHUYÊN MÔN KỂ TỪ KHI TỐT NGHIỆP ĐẠI HỌC Thời gian Nơi công tác Công việc đảm nhiệm Trường Đại học Nguyễn Tất Giảng viên, Khoa Điện-Điện 05/2008 – nay Thành tử ii Luan van CHÂN THÀNH CẢM TẠ Tác giả xin gửi lời tri ân chân thành nhất đến: - Ban Giám Hiệu, Khoa Điện – Điện tử, các Phòng ban liên quan thuộc Trường Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh đã tạo mọi điều kiện học tập và nghiên cứu tốt nhất cho toàn thể Học viên. - Toàn thể Cán bộ giảng dạy đã truyền đạt kiến thức cũng như trang bị cho Học viên nhiều kỹ năng làm việc quý giá. - Ban Giám Hiệu, Khoa Điện-Điện tử Trường Đại Học Nguyễn Tất Thành đã tạo mọi điều kiện tốt nhất giúp bản thân hoàn thành khóa học. - Tiến sĩ Võ Tường Quân – Giảng viên Khoa Cơ khí trường Đại Học Bách Khoa Thành phố Hồ Chí Minh đã tận tâm trong quá trình truyền đạt cũng như hướng dẫn sâu rộng nhiệt tình, đầy trách nhiệm trong suốt thời gian thực thi Luận văn tốt nghiệp.

- Tất cả những người thân yêu trong Gia đình, cùng những thân hữu gần xa đã động viên tinh thần, giúp đỡ về mọi mặt trong suốt hai năm học tập và nghiên cứu. - Tất cả các bạn Học viên cùng khóa đã có nhiều ý kiến đóng góp đúng lúc, kịp thời giúp Luận văn hoàn thành. Trân trọng Thành phố Hồ Chí Minh, tháng 10/2013 Học viên thực hiện Hoàng Hải Sơn iii Luan van LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của tôi. Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác.

Hồ Chí Minh, ngày …tháng …. Tín hiệu GPS từ vệ tinh được Modun GPS thu nhận và đưa vào máy tính xử lí. Phần mềm được viết sẽ lấy được kinh độ và vĩ độ tại vì trí ta đang đứng. Tín hiệu này sẽ được đưa lên bản đồ Google để xác định vị trí trên bản đồ.

Thông qua bản đồ Google Map (Earth) ta tìm và vẽ được đường đi ngắn nhất từ vị trí ta đang đứng tới vị trí ta muốn di chuyển tới. Đường đi này sẽ được băm nhỏ thành các tọa độ và được đưa và Vi điều khiển PIC điều khiển Robot chạy theo đúng lộ trình (Kết hợp với cảm biến la bàn CMPS 03). Trong qua trình di chuyển của Robot, khi chạy tới điểm tiếp theo thì Vi điều khiển sẽ so sánh tọa độ hiện tại (lấy từ GPS) với tọa độ mong muốn (lấy từ bản đồ Google). Nếu trùng thì di chuyển tới điểm tiếp theo, nếu không trùng thì Robot sẽ tự chạy dò cho tới khi trùng tọa độ mong muốn.

Robot cứ chạy qua các điểm và cuối cùng sẽ tới điểm đích đúng theo yêu cầu đưa ra. Robot được ứng dụng trong việc di chuyển tự động trong tương lai sau này. Tác giả Hoàng Hải Sơn v Luan van ABSTRACT  The thesis research on GPS and controllers for robot path before running through the map Google Map (Earth). GPS signals from the GPS satellite receiver module to receive and put into the computer processor.

Software was written to get the longitude and latitude in the position we are standing. This signal will be taken to Google maps to locate on the map. Through the map Google Map (Earth) and we find the shortest path is drawn from one position to the standing position we want to move to. This path will be shredded into the given coordinates and PIC microcontroller and robot control run according to schedule (Combined with compass sensor CMPS 03).

In the process of moving the robot, while running to the next point, the microcontroller will compare current coordinates (from GPS) to the desired coordinates (taken from Google maps). If the insect is moving to the next point, if not identical, the robot will automatically run duplicate detection until the desired coordinates. Robot on the run over the final point and destination to satisfy the requirements given. Robot applications in the automatic transfer of the latter in the future.

Author Hoang Hai Son vi Luan van DANH SÁCH CÁC HÌNH VẼ HÌNH TRANG Hình 1.1 Chùm vệ tinh GPS .2 Các thành phần của GPS .3 Sơ đồ hoạt động của hệ thống GPS Tracking .1 Sơ đồ chân Vi điều khiển 16F887 .2 Các thành phần hệ thống GPS .3 Chòm sao các vệ tinh GPS. 4 Sơ đồ vi ̣trí các tra ̣m điề u khiể n .5 Tổ ng quan bô ̣ phâ ̣n điề u khiể n .6 Bộ phận sử dụng .7 Nguyên tắc định vị từ 2 vệ tinh .8 Nguyên tắc định vị từ 3 vệ tinh .1 Sơ đồ chân cảm biến la bàn .2 Modun GPS EM - 410 .3 Sơ đồ chân Module GPS. Sơ đồ nguyên lí mạch công suất dùng L298. Khối điều khiển trung tâm dùng PIC 16F887.

Sơ đồ nguyên lí và hình mạch FT RS232. Màn hình LCD 16x2. Mô hình tổng quát của hệ thống. Lưu đồ của hệ thống.

Giao diện phần mềm nhận tín hiệu từ GPS. Thuật toán Dijkstra……………………………………………….44 xii Luan van Hình 3. Đường đi ngắn nhất trên bản đồ .1 Lưu đồ tổng quát của phần mềm điều khiển.2 Lưu đồ quá trình gửi dữ liệu xuống vi điều khiển .3 Lưu đồ tiến trình lấy dữ liệu từ file đường đi .4 Lưu đồ cập nhật hiển thị GPS .5 Nội dung gói tin .6 Lưu đồ điều khiển Robot .1 Giao diện tìm đường đi ngắn nhất và phân thành nhiều điểm .2 Giao diện truyền dữ liệu xuống vi điều khiển .3 Hình ảnh Robot di chuyển bám theo tọa độ .4 Đường đi của Robot.56 DANH SÁCH CÁC BẢNG BẢNG TRANG Bảng 3.1 Chức năng các chân cảm biến la bàn………………………………28 Bảng 3.2 Bảng chức năng chuỗi tín hiệu đọc từ GPS………………….3 Chức năng các chân của LCD 16x2……………………………….38 xiii Luan van Giải thuật tìm đường đi ngắn nhất GPS ứng dụng trong giao thông MỤC LỤC MỤC LỤC. 3 CHƢƠNG 1: TỔNG QUAN .1 Tổng quan chung về lĩnh vực nghiên cứu, các kết quả nghiên cứu trong và ngoài nước đã công bố.1 Tổng quan về GPS .2 Các thành phần GPS .3 Các ứng dụng của hệ thống định vị GPS .4 Các công trình nghiên cứu đã được công bố .2 Mục tiêu, khách thể và đối tượng nghiên cứu.2 Khách thể và đối tượng nghiên cứu .3 Nhiệm vụ của đề tài và phạm vi nghiên cứu.4 Phương pháp nghiên cứu.5 Tóm lược nội dung luận văn, điểm mới so với các công trình khác.

14 CHƢƠNG 2: CƠ SỞ LÝ THUYẾT .1 TỔNG QUAN VỀ VI ĐIỀU KHIỂN PIC .1 Ngôn ngữ lập trình và mạch nạp cho PIC .2 Sơ đồ chân vi điều khiển .2 TỔNG QUAN VỀ GPS .1 Các thành phần của hệ thống .2 Nguyên tắc định vị. 24 CHƢƠNG 3: THIẾT KẾ PHẦN CỨNG VÀ PHẦN MỀM.1 THIẾT KẾ PHẦN CỨNG .1 Cảm biến la bàn CMPS-03.2 Module GPS EM - 410.3 Mạch công suất dùng L298. Võ Tƣờng Quân Trang 1 HVTH: Hoàng Hải Sơn Luan van Giải thuật tìm đường đi ngắn nhất GPS ứng dụng trong giao thông 3.4 Sơ đồ khối xử lý trung tâm .5 Mạch chuyển đổi USB – COM .6 Mạch hiển thị dùng LCD 16x2 .7 MÔ HÌNH TỔNG QUÁT ĐIỀU KHIỂN HỆ THỐNG.8 LƯU ĐỒ CỦA HỆ THỐNG .2 THIẾT KẾ PHẦN MỀM .1 Phần mềm nhận tín hiệu từ GPS .2 Tìm đường đi ngắn nhất trên bảng đồ .3 Phần mềm hiển thị tọa độ dùng bản đồ offline. 47 CHƢƠNG 4: KẾT QUẢ ĐẠT ĐƢỢC .1 NHẬN TÍN HIỆU TỪ GPS VÀ HIỂN THỊ LÊN BẢN ĐỒ .2 TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN BẢN ĐỒ GOOGLE VÀ HIỂN THỊ 51 4.1 Truyền tín hiệu xuống vi điều khiển .2 Cập nhật hiển thị tọa độ GPS .3 Nội dung gói tin gửi và nhận (Protocol) .3 LẬP TRÌNH ĐIỀU KHIỂN ROBOT.

53 CHƢƠNG 5: KẾT LUẬN .1 Kết quả đạt được .1 Tìm đường đi ngắn nhất và truyền tín hiệu xuống Robot .2 Thử nghiệm Robot trên đường đi thực tế .2 Các vấn đề còn tồn tại .3 Hướng phát triển của đề tài. 58 TÀI LIỆU THAM KHẢO. Võ Tƣờng Quân Trang 2 HVTH: Hoàng Hải Sơn Luan van Giải thuật tìm đường đi ngắn nhất GPS ứng dụng trong giao thông LỜI NÓI ĐẦU Cùng với sự phát triển của cuộc sống con người thì những yêu cầu về xác định vị trí là rất quan trọng.