Phần mềm tìm đường đi trên bản đồ phường Phương Mai, quận Đống Đa, Hà Nội | Môn Nhập môn trí tuệ nhân tạo - Đại học Bách Khoa Hà Nội

lOMoAR cPSD| 61552889
ĐẠI HỌC BÁCH KHOA HÀ NỘI
TRƯỜNG CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
──────── * ─────── BÀI TẬP LỚN
MÔN: NHẬP MÔN TRÍ TUỆ NHÂN TẠO
Đề tài: Phần mềm tìm đường đi trên bản đồ
phường Phương Mai, quận Đống Đa, Hà Nội Nhóm: 19 Mã lớp học: 157487
Giáo viên hướng dẫn: PGS.TS Trần Đình Khang Danh
sách sinh viên thực hiện: STT Họ và tên Mã sinh Email viên 1 Vũ Phương Ly 20225039 ly.vp225039@sis.hust.edu.vn 2 Nguyễn Phương Linh 20224871 linh.np224871@sis.hust.edu.vn 3 Nguyễn Đăng Quân 20235406 quan.nd235406@sis.hust.edu.vn lOMoAR cPSD| 61552889 Mục lục
Mục lục ................................................................................................ 1
1. Mô tả bài toán .............................................................................. 2
2. Biểu diễn bài toán ........................................................................ 2
3. Phương pháp tìm kiếm ................................................................ 2
4. Công cụ sử dụng .......................................................................... 4
5. Kết quả ........................................................................................ 4
6. Phụ lục: Hướng dẫn cài đặt và khởi chạy .................................... 6 1 lOMoAR cPSD| 61552889 1. Mô tả bài toán
- Xét một mảnh bản đồ của phường Phương Mai, quận Đống Đa, Hà Nội. Bài toán yêu
cầu tìm đường đi giữa 2 điểm A và B bất kỳ và biểu diễn đường đi đó trên bản đồ.
- Ràng buộc: Chỉ được phép đi trên các tuyến đường, không được phép đi xuyên qua các công trình.
2. Biểu diễn bài toán
- Trạng thái bài toán: {(lat, lng)}, trong đó lat tương ứng với vĩ độ, lng tương ứng với
kinh độ. Các trạng thái này sẽ bao gồm tất cả các giao lộ trên mảnh bản đồ.
- Việc xác định trạng thái bài toán như vậy sẽ đảm bảo đường đi tìm được luôn thỏa mãn
ràng buộc: “Chỉ được phép đi trên các tuyến đường, không được phép đi xuyên qua các công trình”.
- Tập các hành động: Di chuyển qua các cạnh nối với đỉnh của trạng thái hiện tại.
Tổng cộng đồ thị bao gồm 5085 đỉnh và 10299 cạnh. Do đồ thị là đồ thị vô hướng liên
thông nên luôn luôn có thể tìm ra ít nhất 1 đường đi ngắn nhất giữa 2 đỉnh.
3. Phương pháp tìm kiếm
- Đầu vào bài toán: Tọa độ của điểm đầu và điểm cuối trên bản đồ do người dùng chọn.
- Đầu ra bài toán: Đường đi ngắn nhất giữa 2 điểm đó.
Phương pháp tìm kiếm: lOMoAR cPSD| 61552889
• Bước 1: Xác định trạng thái đầu, trạng thái đích.
Xác định các trạng thái: Với mỗi điểm đã chọn, duyệt qua tất cả các node trong bản đồ
để tìm 2 node tương ứng có khoảng cách theo đường chim bay ngắn nhất đến node đã
chọn, đồ thị giới hạn khoảng cách giữa 2 node liên tiếp bằng 6 giúp giảm thiểu chênh lệch
so với thực tế, tọa độ của các node này tương ứng sẽ là trạng thái đầu và trạng thái đích của bài toán.
• Bước 2: Tìm đường đi từ trạng thái đầu đến trạng thái đích:
Sử dụng thuật toán A* với hàm đánh giá: f(n) = g(n) + h(n) Trong đó:
+ g(n) là tổng khoảng cách đường đi thực tế từ trạng thái đầu đến trạng thái đang xét
+ h(n) là khoảng cách ước lượng heuristic (khoảng cách đường chim bay) từ trạng thái
đang xét đến trạng thái đích, được tính theo công thức Haversine:
Giả sử trạng thái đích là (lat2, lng2), trạng thái hiện tại là (lat1, lng1), ta có:
+ h(n) = acos(sin(lat1)*sin(lat2)+cos(lat1)*cos(lat2)*cos(lng2-lng1))*6371
Mô tả chi tiết thuật toán: 1. Khởi tạo
- Bắt đầu từ điểm xuất phát, đưa nó vào hàng đợi ưu tiên với chi phí bằng 0. Thiết
lập các bảng để lưu đường đi và chi phí thực tế từ điểm bắt đầu đến từng đỉnh. 2. Duyệt đồ thị
- Lặp qua các đỉnh trong hàng đợi, luôn chọn đỉnh có chi phí ước lượng nhỏ nhất
(tổng chi phí thực tế và chi phí ước lượng đến đích). 3. Tính toán chi phí
- Với mỗi đỉnh kề, tính chi phí thực tế từ điểm bắt đầu đến đó và cộng với chi phí
ước lượng từ đó đến đích. Nếu đường đi mới này ngắn hơn hoặc chưa từng được
xét đến, cập nhật thông tin và đưa vào hàng đợi. 4. Kết thúc
- Khi đỉnh đích được lấy ra khỏi hàng đợi, quá trình tìm kiếm kết thúc. 5. Truy vết đường đi lOMoAR cPSD| 61552889
- Dựa vào bảng lưu cha (father), truy ngược từ đích về nguồn để dựng lại đường đi ngắn nhất. 6. Trả kết quả
- Trả về tổng chi phí thực tế và danh sách các đỉnh trên đường đi ngắn nhất.
4. Công cụ sử dụng
- Ngôn ngữ lập trình: Python - Thư viện:
+ OSMnx: Tải và xử lý dữ liệu bản đồ từ OpenStreetMap, xây dựng đồ thị đường
bộ. Tuy nhiên, do dữ liệu của OpenStreetMap không đủ chi tiết dẫn đến việc
chọn điểm và tìm đường bị sai lệch, dữ liệu bản đồ đã được điều chỉnh bằng
cách chia nhỏ các đoạn đường để tăng số lượng node sao cho độ dài giữa 2
node không vượt quá 6 mét.
+ Streamlit: Tạo giao diện người dùng tương tác để hiển thị bản đồ và nhập liệu.
+ Folium: Hiển thị bản đồ tương tác với các đường đi và trạng thái giao thông. 5. Kết quả
- Hình ảnh minh họa kết quả bài toán:
Hình 1 - Tìm đường đi ngắn nhất dựa trên 2 điểm ngẫu nhiên lOMoAR cPSD| 61552889
Hình 2 - Tìm đường đi ngắn nhất bằng cách nhập địa chỉ đầu và địa chỉ đích 5 lOMoAR cPSD| 61552889
Hình 3 Thay đổi phương tiện giao thông thành ô tô
6. Phụ lục: Hướng dẫn cài đặt và khởi chạy
Bước 1: Cài đặt Python phiên bản 3.13 trở xuống tại Download Python | Python.org
Bước 2: Khởi chạy Windows Terminal 3 dòng lệnh sau và dán vào cửa sổ Terminal vừa
hiện lên để cài đặt Anaconda curl https://repo.anaconda.com/miniconda/Miniconda3- latest-Windows-x86_64.exe -o
.\miniconda.exe start /wait "" .\miniconda.exe /S del .\miniconda.exe
Bước 3: Cài đặt Visual Code Studio cùng các Extensions gợi ý cho Python
Bước 4: Tải xuống tất cả các file từ thư mục Google Drive này. lOMoAR cPSD| 61552889
Hình 4 - Các file chứa trong thư mục Google Drive
Bước 5: Trong một thư mục mới, chuyển 2 file vừa tải vào, sau đó khởi động VSCode và
bấm tổ hợp phím CTRL + K + O để chuyển đến thư mục mới tạo
Bước 6: Trong VSCODE, nhấn tổ hợp phím CTRL + ~ để mở terminal, sau đó chạy dòng
lệnh sau: conda create --prefix ./venv python=3.12.3
Để kích hoạt môi trường conda vừa tạo, khởi động lại VSCode, nhấn tổ hợp phím
CTRL+SHIFT+P sau đó chọn python: select interpreter rồi chọn dòng có dạng python
3.12.3 conda, sau khi chọn ở dưới góc phải sẽ có dòng chữ 3.12.3 (conda).
Hình 5 - Dòng chữ 3.12.3 (conda) cho thấy VSCode đang chạy trong môi trường conda
Bước 7: Vẫn bằng tổ hợp phím CTRL + ~, mở terminal rồi thực hiện câu lệnh:
conda install -c conda-forge osmnx folium streamlit
Sau khi thực hiện, chờ đến lúc terminal hiện ra dòng chữ “Proceed ([y]/n)?” thì nhập “y”
để tiếp tục việc cài đặt. lOMoAR cPSD| 61552889
Hình 6 - Cửa số terminal xác nhận thực hiện
Hình 7 - Thực hiện cài đặt thành công
Bước 8: Sau khi việc cài đặt các công cụ hoàn tất, khởi chạy ứng dụng bằng câu lệnh
terminal (yêu cầu có kết nối internet) :
streamlit run mapp_app.py
Lúc này, một cửa sổ trình duyệt chứa ứng dụng sẽ tự động được mở lên.
Hình 8 - Ứng dụng khởi chạy thành công