Giải thuật tìm đường đi ngắn nhất ứng dụng GPS trong giao thông

Nội dung text: Giải thuật tìm đường đi ngắn nhất ứng dụng GPS trong giao thông

1. GIẢI THUẬT TÌM ĐƯỜNG ĐI NGẮN NHẤT ỨNG DỤNG GPS TRONG GIAO THÔNG Hoàng Hải Sơn 1 và Võ Tường Quân 2 * 1 Học viên cao học, Khoa Điện - Điện Tử, ĐH Sư phạm Kỹ thuật Tp.HCM; 2 Bộ môn Cơ điện Tử, Khoa Cơ khí Đại học Bách Khoa TP.Hồ Chí Minh. TÓM TẮT: Bài báo này nghiên cứu và thưc nghiệm việc tìm đường đi ngắn nhất thông qua bản đồ Google Maps và truyền tín hiệu xuống điều khiển Robot tự hành di chuyển theo định vị của GPS. Kết quả đạt được giúp ta có thể tìm được đường đi tối ưu thông qua bản đồ Google Maps, thử nghiệm được Robot để kiểm chứng định vị GPS và giám sát được đường đi của Robot trên bản đồ. Kết quả thực nghiệm giúp cho việc phát triển các phương tiện giao thông tự hành không người lái trong tương lai giúp giảm tai nạn giao thông, kẹt xe đang nhức nhối trong thời đại hiện nay. Từ khóa: Định vị toàn cầu GPS, Google Maps API, Robot tự hành dùng GPS. FINDING ALGORITHM SHORTEST PATH GPS APPLICATIONS IN TRAFFIC Hoang Hai Son 1, Vo Tuong Quan 2 * 1 Graduate Students, Faculty of Electrical and Electronic Engineer, University of Technical Education of HCMC 2 Mechatronics department, Faculty of Mechanical Engineering University of technical Ho Chi Minh City. ABSTRACT: This paper studies and empirical finding shortest paths through Google Maps and transmitted signals to control autonomous robots moving in GPS navigation. The results can help us to find the best path through the Google Maps map, the robot experiment to verify GPS positioning and monitoring the path of the robot on the map. The experimental results help to develop self-propelled vehicle not the driver in the future to help reduce traffic accidents, traffic congestion aching today. Keywords: Global Locate GPS, Google Maps API, GPS for autonomous robots. * Contact: Dr.Vo Tuong Quan, Faculty of Mechanical Engineering University of Technical HCMC 1. GIỚI THIỆU Trong quá trình phát triển nhanh chóng máy bay quan sự không người lái, robot tự và toàn diện của khoa học và công nghệ, máy hành hoạt động trong những môi trường độc móc càng ngày càng trở nên thông minh hơn và hại, các tàu lặn tự hành dùng để khảo sát địa được sử dụng nhiều hơn để phục vụ cho con hình ứng dụng trong ngành dầu lửa và rất người về nhiều mặt, quân sự cũng như dân sự. nhiều những ứng dụng cơ giới khác có thể hoạt Nhưng hệ thống cơ giới được sử dụng hiện nay động ở chế độ tự động. Và nền tảng cho những được tự động hóa không ngừng để tạo nên sự ứng dụng cơ giới tự động đó chính là khả năng thuận tiện cho con người cũng cải tiến khả tự định vị. năng hoạt động của hệ thống. Ví dụ như xe hơi được lập trình để chạy tự động theo bản đồ, - 1 -
2. Nhờ định vị kết hợp với bản đồ Google xe hơi tự động chạy theo đường đi khong cần map ta có thể điều khiển các thiết bị (Robot) có người lái. thể di chuyển một cách tự động không cần người lái. Đề tài mở ra hướng cho tương lai là 2. Mô hình tổng quát của hệ thống  Viết phương trình đường thẳng qua 2 điểm A, B và tính hệ số góc của đường thẳng  Robot tự hành sẽ đi từ A tới B dựa vào hệ số góc của đường thẳng AB  Khi tới B vi điều khiển lại yêu cầu máy tính gửi tiếp điểm C và quá trình lặp lại cho tới điểm cuối cùng Begin Yêu cầu tọa độ từ Google Map Nhận xung N tọa độ Y Viết PT đường thẳng qua 2 điiểm A,B Tìm hệ số α của đường thẳng AB Đọc dữ liệu từ la bàn Hình 1: Mô hình tổng quát hệ thống  Tín hiệu tọa độ được thu từ Modun GPS N Hệ số góc la bàn lớn α = α EM 410, chuyển đổi RS232 sang chuẩn AB La bàn hơn hoặc nhỏ hơn USB giao tiếp và được hiển thị trên màn Y ĐK Robot chạy về hệ hình máy tính Chạy thẳng số góc αAB  USB 3G có nhiệm vụ nhận thông tin bản đồ từ Google Map hoặc Google Earth  Tín hiệu từ máy tính được giao tiếp với So sánh tọa độ N GPS và B PIC thông qua mạch chuyển đổi USB – UART Y  Cảm biến la bàn được gắn vào PIC để nhận Hình 2: Lưu đồ điều khiển phần cứng thông tin về hướng đi cho Robot  Mạch được cấp nguồn 12V từ Acqui. 4. Thiết kế phần mềm Nguồn cho cảm biến, LCD và vi điều khiển được cấp qua mạch chuyển 12V sang 5V 4.1 Lưu đồ xử lí tín hiệu từ máy tính dùng IC ổn áp LM35  Tín hiệu điều khiển sẽ được cấp cho mạch Start công suất L298 để điều khiển động cơ cho Robot tự hành chạy theo hướng ta mong Chọn COM UART GPS muốn. GPS UART 3. Thiết kế phần cứng Hiển thị thiết bị Truyền & Nhận với CPU  Đầu tiên vi điều khiển yêu cầu gửi tọa độ và nhận 2 điểm từ máy tính Hình 3: Lưu đồ xử lí tín hiệu - 2 -
3.  Sau khi ta khởi động phần mềm sẽ yêu  Tín hiệu GPS sẽ được xử lí và hiển thị cầu ta chọn cổng COM: 1 cổng cho vị trí của điểm hiện tại lên bản đồ Module nhận tín hiệu từ GPS và 1 google map cổng cho việc truyền dữ liệu (UART)  Tín hiệu đường đi sẽ được truyền cho từ máy tính xuống vi điều khiển vi điều khiển giúp Robot đi đúng theo đường mong muốn 4.2 Lưu đồ quá trình gửi dữ liệu xuống vi Truyền dữ liệu từ file text điều khiển Tạo gói 1:  Để truyền được dữ liệu ta phải chuyển dữ Vị trí bắt đầu & 1 vị trí tiếp theo liệu tọa độ dạng float 4 byte sang dữ liệu dang Byte N Chờ phản hồi  Đầu tiên ta truyền 2 điểm đầu tiên cho vi điều khiển (A,B). Vi điều khiển điều khiển Y Robot đi từ A tới B. Khi tới B máy tính lại Dừng gửi truyền dữ liệu điểm C xuống giúp Robot đi từ B tới C. Cứ tương tự Robot sẽ đi tới N Tín hiệu yêu điểm cuối mong muốn. cầu từ CPU Y Y Còn vị trí tiếp Gói n: 2 vị trí tiếp theo theo không N Dừng tiến trình Hình 4: Lưu đồ truyền dữ liệu 4.3 Lưu đồ tiến trình lấy dữ liệu từ file Dữ liệu – Google map đường đi Tạo đường đi trên google  Dựa vào đường đi ngắn nhất từ Google map với n điểm bất kì map ta băm đoạn đường đi thành n điểm bất kì sau đó ta xuất thành file tọa độ Lưu file text: n điểm  Ta tiến hành đưa file tọa độ lên và truyền 2 điểm đầu tiên A và B. Robot tự hành sẽ Load file dữ liệu di chuyển từ A tới B  Khi tới B vi điều khiển sẽ đưa lệnh lên N Kiểm tra Thông báo lỗi file yêu cầu xuất tọa độ điểm tiếp theo. Máy dữ liệu tính sẽ gửi tọa độ điểm C xuống và Y Robot tự hành tiếp tục di chuyển từ B tới Lưu tất cả dữ liệu vào bộ nhớ C. Trong thời gian này điểm A sẽ được & gửi 1 gói đầu tiên (2 điểm) xóa khỏi bộ nhớ để tránh tràn bộ nhớ của vi điều khiển. N  Quá trình này cứ tiếp tục cho đến điểm Chờ phản hồi cuối cùng Y Xóa 2 điểm vừa gửi Hình 5: Lưu đồ tiến trình lấy dữ liệu từ file đường đi - 3 -
4. Nhận dữ liệu từ GPS Module 4.4 Cập nhật hiển thị tọa độ GPS Check Load N  Cứ sau thời gian 1s tọa độ điểm hiện dữ liệu tại sẽ được cập nhật và hiển thị lên bản Y đồ  Nếu tín hiệu GPS bị mất tức thời thì Up file tọa độ phần mềm sẽ hiển thị tọa độ của điểm cũ trước đó Chờ 1s Hình 6: Lưu đồ hiển thị tọa độ hiện tại 4.5 Nội dung gói tin gửi và nhận (Protocol) Magic Word Len Command Data LRC 2 byte 1 byte 1 byte Max = 20 byte 1 byte Hình 7: Nội dung gói tin  Command: Lệnh truyền hay nhận  Data: Dữ liệu 16 Byte bao gồm 2 điểm  Magic word: Nhận dạng gói tin giao tiếp tọa độ (Chọn là 0xFFAA)  8 Byte đầu tiên: Tọa độ điểm đầu (4  Len: Độ dài các Byte cần lấy. Độ dài này Byte kinh độ và 4 Byte vĩ độ) là độ dài của toàn bộ gói gửi (nhận)  8 byte thứ 2: Tọa độ điểm 2  (4 Byte kinh độ và 4 Byte vĩ  LRC: Check dữ liệu độ) 5. Lưu đồ điều khiển Robot E(xe,ye) Y End  Bước 1: Máy tính xử lí tọa độ thành nhiều điểm và chuyển thành file .txt. Dữ liệu này dạng float (Do tín hiệu tọa độ ta lấy 10 số Y D(xd,yd) X lẻ). Kinh độ và vĩ độ được lưu trữ truyền xuống mỗi tín hiệu tốn mất 4 Byte. Do đó Y α2 tọa độ một điểm ta truyền xuống A(xA,yA) γ C(xc,yc) α X tốn dung lượng mất 8 Byte. O α1  Bước 2: Một lần máy tính truyền xuống 2 Y α1 = β - α β B(x ,y ) α α = γ – α điểm và được PIC lưu trữ vào bộ đệm mất b b X 2 O 16 Byte. Robot sẽ kết hợp với la bàn định hướng để chạy từ A tới B β A(xa,ya) X  Bước 3: Khi tới B trùng với tọa độ GPS O Robot đưa về. Robot sẽ ngừng lại và máy tính lại Start gửi tiếp điểm C và Robot tương tự lại chạy từ B tới C. Cứ vậy Robot chạy tới điểm Hình 8: Lưu đồ điều khiển Robot cuối theo yêu cầu. - 4 -
5. 6. Hình ảnh thực tế Tài liệu tham khảo: [1] Thông tin vệ tinh Phạm Minh Việt, NXB khoa học và kỹ thuật. [2] Nguyễn Thị Phương Hà (2012). Lý thuyết điều khiển hiện đại. NXB Đại học Quốc gia TP.HCM [3] Trần Công Nghị (2009). Tự động hóa tính toán thiết kế tàu. Đại học giao thông vận tải thành phố Hồ Chí Minh. [4] Kalman Filtering Theory and Practice Hình 9: Hình ảnh mô hình Using Matlab-Grewal and Andrews[13] 7. Kết luận [5] Qaiser Iftikhar (2009). VB.NET/C# and JavaScript Communication. The Code Project. 7.1 Những vấn đề còn tồn tại [6] National Marine Electronics Association.  Sai số của Module GPS khi thời tiết The NMEA 0183 Protocol. không tốt quá lớn (Có thể lên tới 10m) gây khó khăn trong việc Robot di [7] J.M.J. Journée (1970). A Simple Method for chuyển Determining the Manoeuvring Indices K and T  Phụ thuộc vào bản đồ Google map nên from Zigzag trial Data. Delft University of luôn phải dùng Online, không có mạng Technology. Internet không dùng được [8] Thor I.Fossen (2011). Guidance and  Cần phải có máy tính xử lí tín hiệu và Control of Vehicles. Department of truyền cho Vi điều khiển Engineering Cybernetics - Norwegian  Hệ thống cơ khí thiết kế chưa tốt nên University of Science and Technology Robot hoạt động chưa đúng hoàn toàn (NTNU), Lecture Notes theo ý muốn (khi di chuyển robot đi không thẳng mà dao động quanh vị trí [9] mong muốn) [10] www.alldatasheet.com/ 7.2 Hướng phát triển [11]  Điều khiển Robot từ xa dùng module RF  Dùng Module Sim (GPRS) để lấy tín hiệu html Internet giúp cho phần cứng gọn nhẹ  Lưu lại lộ trình đường đi và giám sát cho Google Maps Javascript API V3 Reference. thiết bị Google Inc.  Chế tạo các phương tiện giao thông tự động trong tương lai gần. [12] page.php?menu=4&gs_en_product_id=6&gs_e n_product_cnt_id=47 - 5 -
6. BÀI BÁO KHOA HỌC THỰC HIỆN CÔNG BỐ THEO QUY CHẾ ĐÀO TẠO THẠC SỸ Bài báo khoa học của học viên có xác nhận và đề xuất cho đăng của Giảng viên hướng dẫn Bản tiếng Việt ©, TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP. HỒ CHÍ MINH và TÁC GIẢ Bản quyền tác phẩm đã được bảo hộ bởi Luật xuất bản và Luật Sở hữu trí tuệ Việt Nam. Nghiêm cấm mọi hình thức xuất bản, sao chụp, phát tán nội dung khi chưa có sự đồng ý của tác giả và Trường Đại học Sư phạm Kỹ thuật TP. Hồ Chí Minh. ĐỂ CÓ BÀI BÁO KHOA HỌC TỐT, CẦN CHUNG TAY BẢO VỆ TÁC QUYỀN! Thực hiện theo MTCL & KHTHMTCL Năm học 2016-2017 của Thư viện Trường Đại học Sư phạm Kỹ thuật Tp. Hồ Chí Minh.