Áp dụng nhiều thuật toán cho robot tìm đường đi trong mê cung | Báo cáo Môn Trí tuệ nhân tạo - Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh

lOMoAR cPSD| 58778885
TR ƯỜ NG ĐẠ I H Ọ C S Ư PH Ạ M K Ỹ THU Ậ T TP.HCM
K HOA: C Ô NG NGH Ệ TH Ô NG TIN
B Á O C Á O M Ô N H Ọ C
TR Í TU Ệ NH Â N T Ạ O
“Á P D Ụ NG NHI Ề U THU Ậ T TO Á N CHO
ROBOT T Ì M ĐƯỜ NG Đ I TRONG M Ê CUNG ”
H Ọ C K Ỳ 2 - N Ă M H Ọ C: 2024-2025
M Ã L Ớ P H Ọ C PH Ầ N:
Gi ả ng vi ê n h ướ ng d ẫ n: ThS. B ù i M ạ nh Qu â n
Nh ó m sinh vi ê n th ự c hi ệ n:
Tr ầ n Quang Minh - 23110269
Hu ỳ nh Duy Nguy ê n - 23110270
Tr ầ n Tr í T ì nh - 23110341
TP. HCM, th á ng 5 n ă m 2025 lOMoAR cPSD| 58778885
TR ƯỜ NG ĐẠ I H Ọ C S Ư PH Ạ M K Ỹ THU Ậ T TP.HCM
K HOA: C Ô NG NGH Ệ TH Ô NG TIN
B Á O C Á O M Ô N H Ọ C
TR Í TU Ệ NH Â N T Ạ O
“Á P D Ụ NG NHI Ề U THU Ậ T TO Á N CHO
ROBOT T Ì M ĐƯỜ NG Đ I TRONG M Ê CUNG ”
H Ọ C K Ỳ 2 - N Ă M H Ọ C: 2024-2025
M Ã L Ớ P H Ọ C PH Ầ N:
Gi ả ng vi ê n h ướ ng d ẫ n: ThS. B ù i M ạ nh Qu â n
Nh ó m sinh vi ê n th ự c hi ệ n:
Tr ầ n Quang Minh - 23110269
Hu ỳ nh Duy Nguy ê n - 23110270
Tr ầ n Tr í T ì nh - 23110341
TP. HCM, th á ng 5 n ă m 2025 lOMoAR cPSD| 58778885
NHẬN XÉT VÀ ĐÁNH GIÁ CỦA GIẢNG VIÊN
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….…………………………………………………………………………
….………………………………………………………………………… lOMoAR cPSD| 58778885 MỤC LỤC
LỜI NÓI ĐẦU ........................................................................................... 1
CHƯƠNG 1. GIỚI THIỆU ...................................................................... 2
1.1. Lý do chọn đề tài ................................................................................. 2
1.2. Mục tiêu đề tài ..................................................................................... 2
1.3. Phạm vi đề tài ...................................................................................... 3
1.4. Đối tượng nghiên cứu .......................................................................... 3
1.5. Phương pháp nghiên cứu ..................................................................... 4
1.6. Bố cục đề tài ........................................................................................ 4
CHƯƠNG 2. CƠ SỞ LÝ THUYẾT ........................................................ 4
2.1. Các thuật toán tìm kiếm đường đi: ...................................................... 4
2.1.1. Thuật toán tìm kiếm theo chiều sâu (DFS):...................................... 5
2.1.2. Thuật toán tìm kiếm theo chiều rộng (BFS): .................................... 6
2.1.3. Thuật toán A*: .................................................................................. 7
2.1.4. Thuật toán Dijkstra: .......................................................................... 7
2.1.5. Thuật toán tìm kiếm sâu dần (IDDFS): ............................................ 8
2.1.6. Thuật toán tìm kiếm ưu tiên tốt nhất (Best First Search): ................ 9
2.1.7. Thuật toán tìm kiếm theo chùm (Beam Search): .............................. 9
2.1.8. Thuật toán tìm kiếm theo điểm nhảy (Jump Point Search - JPS): .. 10
2.1.9. Thuật toán A* hai hướng (Bidirectional A*): ................................. 11
2.2. Sinh mê cung: .................................................................................... 12
2.2.1. Thuật toán Prim: ............................................................................. 12
2.2.3. Thuật toán Backtracking (Đệ quy): ................................................ 13
2.2.4. Thuật toán Cây nhị phân (Binary Tree): ......................................... 14
2.2.5. Thuật toán Aldous-Broder có độ lệch (Biased Aldous-Broder): .... 14
2.3. Bài toán mê cung: .............................................................................. 15
2.3.1. Bài toán mê cung cơ bản: ............................................................... 15
2.3.2. Các yếu tố quan tâm nâng cao: ....................................................... 15
2.3.3. Ảnh hưởng của đặc điểm và yêu cầu bài toán mê cung đến hiệu quả
thuật toán: ................................................................................................. 16
2.4. Yếu tố AI: ........................................................................................... 17
2.4.1. Học máy (Machine Learning): ....................................................... 17
2.4.2. Cây quyết định (Decision Tree):..................................................... 18
2.4.3. Rừng ngẫu nhiên (Random Forest): ............................................... 18
CHƯƠNG 3. TRIỂN KHAI ĐỀ TÀI .................................................... 20
3.1. Bài toán mê cung ............................................................................... 20
3.2. Phân tích bài toán: ............................................................................. 20
3.2.1. Yêu cầu thời gian (Router Mode) ................................................... 20
3.2.2. Yêu cầu chi phí (Collector Mode) .................................................. 22
3.3. Xử lý dữ liệu: ..................................................................................... 23
3.3.1. Thông số hóa mê cung: ................................................................... 23 lOMoAR cPSD| 58778885
3.3.2. Đánh giá hiệu suất thuật toán tìm đường đi: .................................. 25
3.3.3. Học máy và thống kê xử lý thông số: ............................................. 26
3.4. Triển khai ứng dụng: .......................................................................... 27
KẾT LUẬN .............................................................................................. 30
TÀI LIỆU THAM KHẢO ...................................................................... 30 lOMoAR cPSD| 58778885 LỜI NÓI ĐẦU
Trước khi đi vào nội dung chính của đề tài, nhóm xin được gửi lời cảm ơn
chân thành đến thầy Bùi Mạnh Quân – người đã tận tình giảng dạy và
truyền đạt những kiến thức quý báu trong suốt quá trình học tập. Những
bài giảng và hướng dẫn của thầy đã đóng vai trò quan trọng trong việc định
hướng tư duy, giúp nhóm hiểu rõ hơn về các khái niệm, thuật toán và
phương pháp tiếp cận cần thiết để thực hiện đề tài một cách hiệu quả. Nhờ
vào nền tảng kiến thức được trang bị từ môn học, nhóm đã có thể áp dụng
vào việc xây dựng, phân tích và so sánh các thuật toán sinh mê cung và tìm
đường một cách bài bản. Một lần nữa, nhóm xin gửi lời cảm ơn sâu sắc đến
thầy và hy vọng sẽ tiếp tục nhận được sự hỗ trợ và góp ý quý báu trong các đề tài sau. lOMoAR cPSD| 58778885
CHƯƠNG 1. GIỚI THIỆU
1.1. Lý do chọn đề tài
Trong bối cảnh trí tuệ nhân tạo (AI) ngày càng phát triển và được ứng dụng
rộng rãi trong nhiều lĩnh vực như y tế, giao thông, sản xuất, và đặc biệt là
trong lĩnh vực robot học, các hệ thống robot ngày càng được kỳ vọng có
thể hoạt động một cách tự động, thông minh và tối ưu hơn. Một trong những
bài toán cốt lõi trong quá trình phát triển robot thông minh là bài toán tìm
đường đi trong môi trường không xác định như mê cung. Thực tế cho thấy,
trong các nhiệm vụ như robot cứu hộ, vận chuyển hàng hóa trong kho hàng,
hay điều hướng trong không gian phức tạp, robot cần có khả năng xác định
đường đi từ vị trí xuất phát đến đích một cách hiệu quả, chính xác và tối ưu
hóa về tài nguyên. Điều này đặt ra yêu cầu lựa chọn thuật toán tìm đường
phù hợp với từng hoàn cảnh cụ thể. Hiện nay, có nhiều thuật toán tìm đường
đã được phát triển như BFS, DFS, Dijkstra, A*, Greedy Best-First
Search,… Mỗi thuật toán có ưu nhược điểm riêng về hiệu quả tìm kiếm,
thời gian tính toán, độ dài đường đi và mức sử dụng bộ nhớ. Tuy nhiên,
việc lựa chọn thuật toán nào là tốt nhất cho một loại mê cung cụ thể vẫn là
vấn đề mở. Do đó, đề tài “Áp dụng nhiều thuật toán cho robot tìm đường
đi trong mê cung” ra đời nhằm phân tích, đánh giá và tìm ra hướng lựa chọn
thuật toán tối ưu theo từng trường hợp, từ đó có thể ứng dụng rộng rãi vào
các hệ thống robot AI trong thực tế.
1.2. Mục tiêu đề tài
Đề tài hướng đến việc xây dựng một hệ thống mô phỏng cho phép robot
tìm đường đi trong mê cung bằng cách áp dụng và so sánh nhiều thuật toán tìm kiếm khác nhau. Mục tiêu cụ thể gồm:
Xây dựng hệ thống mô phỏng quá trình robot tìm đường trong mê cung. ⚫ lOMoAR cPSD| 58778885
Cài đặt và triển khai một số thuật toán tìm đường phổ biến như BFS, ⚫
DFS, Dijkstra, A*,Greedy Best-First Search,...
Đánh giá hiệu quả từng thuật toán qua các tiêu chí: độ dài đường đi, ⚫
thời gian xử lý, số bước tìm kiếm, và tài nguyên sử dụng.
Đưa ra đề xuất thuật toán tối ưu cho từng loại mê cung dựa trên kết quả ⚫ đánh giá.
Hệ thống có thể phục vụ cho mục đích học thuật, nghiên cứu thuật toán,
hoặc là nền tảng cho các ứng dụng thực tế như robot cứu hộ, xe tự hành
trong môi trường có cấu trúc mê cung.
1.3. Phạm vi đề tài
Đề tài tập trung nghiên cứu và thử nghiệm các thuật toán tìm đường trong phạm vi sau:
Môi trường là các mê cung hai chiều có cấu trúc tĩnh (không thay đổi ⚫ theo thời gian).
Không xét đến các yếu tố vật lý của robot như vận tốc, năng lượng, ⚫
hoặc điều kiện môi trường thực tế.
Các thuật toán được triển khai và thử nghiệm trên phần mềm mô phỏng, ⚫
không áp dụng vào robot vật lý.
Không sử dụng các phương pháp học sâu (deep learning) hay thuật toán ⚫
tối ưu nâng cao như GA, Q-learning,...
Việc giới hạn phạm vi giúp đảm bảo đề tài thực hiện được trong thời gian
cho phép, đồng thời tập trung phân tích sâu các thuật toán cổ điển.
1.4. Đối tượng nghiên cứu
Các đối tượng được nghiên cứu trong đề tài bao gồm:
Các thuật toán tìm đường như BFS, DFS, Dijkstra, A*, Greedy Best- ⚫ First Search.
Các thuật toán sinh mê cung để tạo môi trường thử nghiệm đa dạng. ⚫
Hệ thống mô phỏng robot và môi trường mê cung trong không gian hai ⚫ chiều. lOMoAR cPSD| 58778885
Các tiêu chí đánh giá thuật toán như hiệu năng, độ chính xác, tốc độ xử lý.
1.5. Phương pháp nghiên cứu
Để thực hiện đề tài, các phương pháp nghiên cứu sau được sử dụng:
Phương pháp thu thập thông tin: Nghiên cứu tài liệu học thuật, giáo ⚫
trình, bài báo khoa học để tìm hiểu các thuật toán tìm đường và mô hình mô phỏng.
Phương pháp xử lý thông tin: Phân tích, so sánh đặc điểm kỹ thuật của ⚫
từng thuật toán dựa trên các thông số định lượng như thời gian chạy, số
lượng nút duyệt qua, độ dài đường đi.
Phương pháp thực nghiệm: Cài đặt các thuật toán bằng Python (sử dụng ⚫
thư viện hỗ trợ đồ họa như Pygame), thiết kế nhiều loại mê cung khác
nhau để kiểm thử và thu thập dữ liệu.
Phương pháp phân tích định tính: Đánh giá ưu – nhược điểm từng thuật ⚫
toán trong từng bối cảnh để rút ra kết luận.
1.6. Bố cục đề tài
Phần còn lại của báo cáo tiểu luận được tổ chức như sau:
Chương 2 trình bày cơ sở lý thuyết liên quan đến đề tài, bao gồm tổng quan
về các thuật toán tìm đường, các kỹ thuật sinh mê cung và các tiêu chí đánh
giá hiệu suất thuật toán. Bên cạnh đó, chương này cũng phân tích những
nghiên cứu trước có liên quan và định hướng nghiên cứu của đề tài.
Chương 3 trình bày quá trình triển khai mô hình mô phỏng, cách thức cài
đặt các thuật toán tìm đường và sinh mê cung. Ngoài ra, chương này còn
mô tả phương pháp thử nghiệm, thiết kế kịch bản mô phỏng và thu thập kết quả.
CHƯƠNG 2. CƠ SỞ LÝ THUYẾT
2.1. Các thuật toán tìm kiếm đường đi:
Trong dự án này, nhóm đã triển khai và nghiên cứu một tập hợp đa dạng
các thuật toán tìm kiếm đường đi, từ những phương pháp cơ bản đến các lOMoAR cPSD| 58778885
kỹ thuật nâng cao. Mục tiêu là xây dựng một hệ thống cho phép robot tự
động tìm kiếm lộ trình tối ưu trong mê cung, đồng thời cung cấp một nền
tảng để so sánh hiệu suất và đặc điểm của từng thuật toán. nhóm đặc biệt
chú trọng vào việc tinh chỉnh và tối ưu hóa các thuật toán này để giải quyết
hiệu quả các thách thức cụ thể của bài toán tìm đường trong mê cung, bao
gồm việc giảm thiểu số bước di chuyển, tối ưu hóa thời gian thực thi và
nâng cao khả năng xử lý các mê cung có độ phức tạp khác nhau.
2.1.1. Thuật toán tìm kiếm theo chiều sâu (DFS):
Nguyên lý hoạt động: DFS là một thuật toán duyệt đồ thị bắt đầu tại một
nút gốc (trong trường hợp này là điểm xuất phát của robot) và khám phá
càng sâu càng tốt dọc theo mỗi nhánh trước khi quay lui. Thuật toán sử
dụng một stack để theo dõi các nút cần duyệt. Khi một nút được thăm, các
nút lân cận chưa được thăm của nó sẽ được đưa vào stack và quá trình lặp lại. Ưu điểm:
Tiêu thụ ít bộ nhớ hơn BFS trong trường hợp đồ thị sâu. ⚫
Có thể tìm thấy đường đi đến mục tiêu nhanh chóng nếu mục tiêu nằm ⚫
sâu trong đồ thị theo một nhánh cụ thể.
Dễ dàng cài đặt bằng đệ quy. ⚫ Nhược điểm:
Có thể không tìm thấy đường đi ngắn nhất. ⚫
Có nguy cơ rơi vào vòng lặp vô hạn trong đồ thị có chu trình nếu không ⚫
có cơ chế kiểm soát duyệt hiệu quả.
Ứng dụng: Tìm đường đi trong các trò chơi giải đố, duyệt cây thư mục. Cải
tiến cho đề tài: Để khắc phục nhược điểm của DFS trong môi trường mê
cung, nhóm đã triển khai một cách tiếp cận không đệ quy sử dụng stack
một cách tường minh. Quan trọng hơn, nhóm đã tích hợp một tập hợp visit
để theo dõi các ô đã duyệt, ngăn chặn việc посещение lại các ô và tránh lOMoAR cPSD| 58778885
các vòng lặp vô hạn. Đồng thời, nhóm duy trì một danh sách path để lưu
trữ đường đi hiện tại từ điểm bắt đầu, cho phép truy vết lại lộ trình khi đạt
được mục tiêu. Việc này đảm bảo rằng thuật toán sẽ dừng lại khi tìm thấy
mục tiêu và cung cấp đường đi đã tìm được.
2.1.2. Thuật toán tìm kiếm theo chiều rộng (BFS):
Nguyên lý hoạt động: BFS duyệt đồ thị theo từng mức. Bắt đầu từ nút gốc,
nó khám phá tất cả các nút lân cận ở mức hiện tại trước khi chuyển sang
các nút ở mức tiếp theo. Thuật toán sử dụng một hàng đợi (queue) để quản lý các nút cần duyệt. Ưu điểm:
Đảm bảo tìm thấy đường đi ngắn nhất (về số lượng cạnh) trong đồ thị ⚫ không có trọng số.
Hoàn toàn và sẽ tìm thấy mục tiêu nếu nó tồn tại. ⚫ Nhược điểm:
Có thể tiêu thụ nhiều bộ nhớ hơn DFS trong trường hợp đồ thị rộng. ⚫
Có thể mất nhiều thời gian hơn để tìm thấy mục tiêu nếu mục tiêu nằm ⚫ sâu trong đồ thị.
Ứng dụng: Tìm đường đi ngắn nhất trong các hệ thống định vị, duyệt các
mối quan hệ trong mạng xã hội.
Cải tiến cho đề tài: Trong triển khai BFS, nhóm đã sử dụng deque (double-
ended queue) từ thư viện collections của Python để thực hiện các thao tác
thêm và xóa ở cả hai đầu một cách hiệu quả, tối ưu hóa hiệu suất của hàng
đợi. Mỗi phần tử trong hàng đợi chứa một tuple gồm vị trí hiện tại và đường
đi đã đi qua để đến vị trí đó. Nhóm cũng duy trì một danh sách visited để
theo dõi các ô đã duyệt, tránh việc посещение lại và đảm bảo hiệu suất của
thuật toán. Khi đạt được ô mục tiêu, đường đi được lưu trữ cùng với vị trí
đó sẽ được trả về. lOMoAR cPSD| 58778885
2.1.3. Thuật toán A*:
Nguyên lý hoạt động: A* là một thuật toán tìm kiếm informed (có thông
tin) sử dụng hàm đánh giá f(n)=g(n)+h(n), trong đó g(n) là chi phí đã đi từ
nút bắt đầu đến nút n, và h(n) là một hàm heuristic ước tính chi phí từ nút
n đến nút mục tiêu. Thuật toán sử dụng một hàng đợi ưu tiên (priority
queue) để chọn nút có giá trị f(n) thấp nhất để khám phá tiếp theo. Ưu điểm:
Hiệu quả hơn các thuật toán uninformed như BFS và Dijkstra trong ⚫
nhiều trường hợp do sử dụng thông tin heuristic.
Có khả năng tìm thấy đường đi tối ưu nếu hàm heuristic là admissible ⚫
(không bao giờ đánh giá quá cao chi phí thực tế). Nhược điểm:
Hiệu suất phụ thuộc lớn vào chất lượng của hàm heuristic. Một hàm ⚫
heuristic không tốt có thể dẫn đến hiệu suất kém.
Có thể tiêu thụ nhiều bộ nhớ hơn DFS. ⚫
Ứng dụng: Lập kế hoạch đường đi cho robot, tìm đường đi trong game AI.
Cải tiến cho đề tài: nhóm đã triển khai hàm heuristic Manhattan distance
(self.heuristic) để ước tính chi phí di chuyển giữa hai ô trong mê cung (tổng
số bước di chuyển theo chiều ngang và chiều dọc). Việc sử dụng heapq
(heap queue) của Python làm hàng đợi ưu tiên cho phép truy xuất nút có
chi phí f(n) thấp nhất một cách hiệu quả. nhóm cũng duy trì một danh sách
visited để theo dõi các ô đã được khám phá, ngăn chặn việc xử lý lại các
trạng thái và đảm bảo tính hiệu quả của thuật toán.
2.1.4. Thuật toán Dijkstra:
Nguyên lý hoạt động: Dijkstra là một thuật toán tìm kiếm đường đi ngắn
nhất trong đồ thị có trọng số không âm. Nó tương tự như BFS nhưng sử
dụng một hàng đợi ưu tiên để chọn nút có chi phí đường đi từ nút bắt đầu
thấp nhất để khám phá. Trong trường hợp mê cung không có trọng số (mỗi lOMoAR cPSD| 58778885
bước di chuyển có chi phí là 1), Dijkstra tương đương với BFS về việc tìm đường đi ngắn nhất. Ưu điểm:
Tìm đường đi ngắn nhất trong đồ thị có trọng số không âm. ⚫
Hoàn toàn và sẽ tìm thấy mục tiêu nếu nó tồn tại. ⚫ Nhược điểm:
Có thể kém hiệu quả hơn A* nếu một hàm heuristic tốt có sẵn. ⚫
Khám phá các nút theo mọi hướng, ngay cả khi chúng không hướng ⚫ đến mục tiêu.
Ứng dụng: Tìm đường đi ngắn nhất trong mạng lưới giao thông, định tuyến mạng.
Cải tiến cho đề tài: Triển khai Dijkstra của nhóm sử dụng heapq để quản lý
các nút theo chi phí tích lũy từ điểm bắt đầu. Một dictionary visited được
sử dụng để lưu trữ chi phí ngắn nhất đã biết đến mỗi nút, cho phép nhóm
bỏ qua các đường đi dài hơn đến cùng một nút. Danh sách visited_list theo
dõi thứ tự các nút đã được khám phá.
2.1.5. Thuật toán tìm kiếm sâu dần (IDDFS):
Nguyên lý hoạt động: IDDFS kết hợp ưu điểm của DFS (tiết kiệm bộ nhớ)
và BFS (tìm đường đi ngắn nhất trong đồ thị không có trọng số). Nó thực
hiện một loạt các tìm kiếm DFS với độ sâu giới hạn tăng dần. Bắt đầu với
giới hạn độ sâu là 0, sau đó 1, 2, và cứ tiếp tục như vậy cho đến khi tìm thấy mục tiêu. Ưu điểm:
Tìm đường đi ngắn nhất trong đồ thị không có trọng số (tương tự BFS). ⚫
Tiêu thụ ít bộ nhớ hơn BFS. ⚫
Hiệu quả hơn BFS trong trường hợp không gian tìm kiếm rộng nhưng ⚫
giải pháp nằm ở độ sâu nông. Nhược điểm: lOMoAR cPSD| 58778885
Có thể tốn thời gian hơn BFS vì phải thực hiện lại việc tìm kiếm ở các ⚫ mức độ sâu khác nhau.
Ứng dụng: Tìm đường đi trong các trò chơi có không gian trạng thái lớn,
kiểm tra tính khả năng giải quyết của các bài toán tìm kiếm. Cải tiến cho
đề tài: Triển khai IDDFS của nhóm sử dụng một hàm đệ quy DLS (Depth-
Limited Search) được gọi lặp đi lặp lại với độ sâu giới hạn tăng dần. Danh
sách visit được sử dụng để theo dõi các nút đã duyệt trong mỗi lần gọi DLS.
Quá trình tìm kiếm tiếp tục cho đến khi tìm thấy mục tiêu hoặc đạt đến một
độ sâu giới hạn hợp lý (trong trường hợp này là tích của số hàng và số cột của mê cung).
2.1.6. Thuật toán tìm kiếm ưu tiên tốt nhất (Best First Search):
Nguyên lý hoạt động: Best First Search là một thuật toán tìm kiếm informed
sử dụng hàm heuristic để ước tính độ "hứa hẹn" của một nút.
Nó mở rộng các nút có giá trị heuristic thấp nhất. Ưu điểm:
Có thể tìm thấy đường đi đến mục tiêu nhanh chóng nếu hàm heuristic ⚫ tốt. Nhược điểm:
Không đảm bảo tìm thấy đường đi ngắn nhất. ⚫
Có thể bị mắc kẹt trong các ngõ cụt nếu hàm heuristic không chính xác. ⚫
Ứng dụng: Các bài toán tìm đường trong đó tốc độ là ưu tiên hơn tính ⚫
tối ưu của đường đi.
Cải tiến cho đề tài: nhóm sử dụng heapq để ưu tiên các nút có giá trị
heuristic Manhattan distance thấp nhất. Danh sách visited theo dõi các nút
đã duyệt để tránh lặp lại.
2.1.7. Thuật toán tìm kiếm theo chùm (Beam Search):
Nguyên lý hoạt động: Beam Search là một thuật toán tìm kiếm heuristic mà
tại mỗi mức độ của cây tìm kiếm, nó chỉ giữ lại một số hữu hạn các trạng lOMoAR cPSD| 58778885
thái "tốt nhất" (được xác định bởi một hàm đánh giá heuristic), được gọi là
"chùm" (beam). Các trạng thái còn lại bị loại bỏ. Ưu điểm:
Giảm đáng kể không gian tìm kiếm so với các thuật toán tìm kiếm rộng ⚫ hơn.
Thường tìm thấy giải pháp chấp nhận được trong thời gian ngắn. ⚫ Nhược điểm:
Không đảm bảo tìm thấy đường đi tối ưu. ⚫
Có nguy cơ bỏ lỡ giải pháp nếu các trạng thái tốt nhất ban đầu không dẫn đến mục tiêu.
Ứng dụng: Các bài toán tối ưu hóa, nhận dạng tiếng nói.
Cải tiến cho đề tài: nhóm đã triển khai Beam Search với một độ rộng chùm
(beam_width) có thể điều chỉnh để kiểm soát số lượng trạng thái được xem
xét tại mỗi bước. Để tăng cường khả năng tìm thấy mục tiêu, nhóm đã thêm
cơ chế tăng dần beam_width nếu không tìm thấy tiến triển sau một số bước
nhất định. Ngoài ra, nhóm duy trì một dictionary all_paths để theo dõi
đường đi đến từng nút, cho phép thực hiện quay lui (backtracking) nếu
chùm hiện tại không dẫn đến mục tiêu. Việc theo dõi các ngõ cụt
(dead_ends) giúp tránh lãng phí tài nguyên vào các khu vực không có lối
thoát. Trong trường hợp Beam Search thất bại, nhóm đã tích hợp cơ chế dự
phòng quay lại thuật toán A* để đảm bảo tìm được đường đi nếu có.
2.1.8. Thuật toán tìm kiếm theo điểm nhảy (Jump Point Search JPS):
Nguyên lý hoạt động: JPS là một thuật toán tối ưu hóa cho A* trên các lưới
ô vuông. Nó giảm số lượng nút cần xem xét bằng cách "nhảy" qua các nút
không quan trọng dọc theo các đường thẳng (ngang, dọc, chéo). Nó xác
định các "điểm nhảy" (jump points) là các nút quan trọng cần được khám phá. Ưu điểm: lOMoAR cPSD| 58778885
Giảm đáng kể số lượng nút được khám phá so với A*. ⚫
Cải thiện đáng kể hiệu suất về thời gian và bộ nhớ trên các lưới ô vuông. ⚫ Nhược điểm:
Phức tạp hơn để cài đặt so với A* tiêu chuẩn. ⚫
Ứng dụng: Lập kế hoạch đường đi hiệu quả trong game AI và các ứng dụng robot trên lưới.
Cải tiến cho đề tài: nhóm đã triển khai các hàm identify_successors và jump
để xác định các điểm nhảy từ một nút hiện tại. Hàm jump đệ quy tìm kiếm
dọc theo một hướng cho đến khi gặp một vật cản, một nút mục tiêu hoặc
một nút có "hàng xóm bị ép" (forced neighbor) – một nút mà đường đi ngắn
nhất đến đó phải đi qua nút hiện tại. Việc này giúp bỏ qua nhiều nút trung
gian không cần thiết, dẫn đến việc tìm kiếm nhanh hơn.
Hàm has_forced_neighbors xác định các nút lân cận bị ép.
2.1.9. Thuật toán A* hai hướng (Bidirectional A*):
Nguyên lý hoạt động: Bidirectional A* tìm kiếm đồng thời từ cả nút bắt
đầu và nút mục tiêu. Hai tìm kiếm A* chạy song song cho đến khi chúng
gặp nhau ở một nút nào đó. Đường đi từ nút bắt đầu đến điểm gặp và đường
đi đảo ngược từ nút mục tiêu đến điểm gặp được kết hợp để tạo thành đường đi hoàn chỉnh. Ưu điểm:
Có thể giảm đáng kể không gian tìm kiếm so với A* một hướng, đặc ⚫
biệt trong các không gian tìm kiếm rộng. Nhược điểm:
Điều kiện kết thúc có thể phức tạp hơn. ⚫
Việc kết hợp hai đường đi có thể đòi hỏi thêm bước xử lý. ⚫
Ứng dụng: Các bài toán tìm đường đi trong không gian lớn.
Cải tiến cho đề tài: nhóm duy trì hai hàng đợi ưu tiên (open_f, open_b), hai
tập hợp các nút đã đóng (closed_f, closed_b), và hai dictionary lưu trữ chi
phí (g_f, g_b) và cha (parent_f, parent_b) cho cả hai hướng tìm kiếm. Thuật lOMoAR cPSD| 58778885
toán dừng lại khi một nút được mở bởi một hướng tìm kiếm đã được duyệt
bởi hướng tìm kiếm kia. nhóm theo dõi chi phí đường đi tốt nhất
(best_path_cost) và điểm gặp nhau (meeting_point) để đảm bảo tìm được
đường đi tối ưu. Sau khi tìm thấy điểm gặp, nhóm tái tạo đường đi bằng
cách truy vết ngược lại từ điểm gặp về cả điểm bắt đầu và điểm kết thúc.
Thông qua việc triển khai chi tiết và tích hợp các cải tiến này, dự án của
nhóm không chỉ mô phỏng quá trình tìm đường đi của robot trong mê cung
mà còn cung cấp một công cụ hữu ích để so sánh hiệu suất, đánh giá ưu
nhược điểm và hiểu rõ hơn về cách các thuật toán tìm kiếm đường đi khác
nhau hoạt động trong cùng một môi trường. Những cải tiến này đặc biệt tập
trung vào việc tăng cường tính hiệu quả, độ tin cậy và khả năng xử lý các
tình huống phức tạp trong bài toán tìm đường đi trong mê cung. 2.2. Sinh mê cung:
Để tạo ra môi trường thử nghiệm đa dạng cho robot tìm đường, nhóm đã
triển khai năm thuật toán sinh mê cung phổ biến: thuật toán Prim, thuật
toán Wilson, thuật toán Backtracking (đệ quy), thuật toán Cây nhị phân và
thuật toán Aldous-Broder có độ lệch. Mỗi thuật toán này có nguyên lý hoạt
động riêng và tạo ra các loại mê cung với đặc điểm cấu trúc khác nhau, từ
đó ảnh hưởng đến độ khó và hiệu suất của các thuật toán tìm đường.
2.2.1. Thuật toán Prim:
Nguyên lý hoạt động: Thuật toán Prim bắt đầu với một ô ngẫu nhiên trong
lưới và xem nó như một phần của mê cung. Sau đó, nó duy trì một tập hợp
các ô biên (frontier cells) là các ô tường liền kề với các ô đã thuộc mê cung.
Tại mỗi bước, thuật toán chọn ngẫu nhiên một ô biên và kết nối nó với một
ô ngẫu nhiên đã thuộc mê cung bằng cách "đục thủng" bức tường giữa
chúng. Ô biên được chọn sau đó trở thành một phần của mê cung, và các ô
tường lân cận chưa được duyệt của nó được thêm vào tập hợp các ô biên.
Quá trình này lặp lại cho đến khi tất cả các ô đều thuộc về mê cung. lOMoAR cPSD| 58778885
Đặc điểm mê cung: Thuật toán Prim thường tạo ra các mê cung có nhiều
đường ngắn và nhiều ngã rẽ, với cấu trúc tương đối phức tạp và nhiều
đường cụt ngắn. Mê cung có xu hướng có độ "xoắn" cao.
2.2.2. Thuật toán Wilson:
Nguyên lý hoạt động: Thuật toán Wilson sử dụng một phương pháp dựa
trên các bước đi ngẫu nhiên không tạo vòng lặp. Nó bắt đầu với một ô bất
kỳ chưa thuộc mê cung và thực hiện một bước đi ngẫu nhiên đến một ô lân
cận chưa duyệt. Quá trình này tiếp tục cho đến khi bước đi ngẫu nhiên chạm
vào một ô đã thuộc mê cung. Đường đi đã tạo ra trong quá trình bước đi
ngẫu nhiên (bao gồm cả các vòng lặp đã được loại bỏ) sau đó được thêm
vào mê cung bằng cách "đục thủng" các bức tường dọc theo đường đi đó.
Quá trình này lặp lại cho đến khi tất cả các ô đều thuộc về mê cung.
Đặc điểm mê cung: Thuật toán Wilson tạo ra các mê cung có cấu trúc đồng
đều hơn so với thuật toán Prim, với ít đường cụt ngắn hơn và các đường đi
dài hơn, ít "xoắn" hơn. Mê cung có xu hướng trông tự nhiên và không có
sự thiên vị rõ rệt về hướng.
2.2.3. Thuật toán Backtracking (Đệ quy):
Nguyên lý hoạt động: Thuật toán Backtracking bắt đầu tại một ô ngẫu nhiên
và đánh dấu nó là đã duyệt. Sau đó, nó chọn ngẫu nhiên một ô lân cận chưa
duyệt và di chuyển đến đó, "đục thủng" bức tường giữa hai ô. Ô mới trở
thành ô hiện tại, và quá trình lặp lại. Nếu ô hiện tại không có bất kỳ ô lân
cận chưa duyệt nào, thuật toán "quay lui" (backtrack) về ô trước đó và thử
một hướng khác. Quá trình này tiếp tục cho đến khi tất cả các ô đều đã được duyệt.
Đặc điểm mê cung: Thuật toán Backtracking thường tạo ra các mê cung có
một đường đi dài, quanh co từ điểm bắt đầu đến điểm kết thúc, với rất ít
hoặc không có vòng lặp. Mê cung có xu hướng có nhiều đường cụt dài. lOMoAR cPSD| 58778885
2.2.4. Thuật toán Cây nhị phân (Binary Tree):
Nguyên lý hoạt động: Thuật toán Cây nhị phân là một thuật toán sinh mê
cung đơn giản. Đối với mỗi ô trong lưới (trừ các ô ở biên phía bắc và phía
tây), thuật toán ngẫu nhiên quyết định "đục thủng" một bức tường về phía
bắc hoặc về phía tây. Điều này tạo ra một cấu trúc giống như cây nhị phân.
Đặc điểm mê cung: Thuật toán Cây nhị phân tạo ra các mê cung có cấu trúc
rất đặc trưng, với các đường đi chủ yếu theo một hướng (ví dụ: đôngnam).
Mê cung thường có nhiều đường cụt theo hướng ngược lại (ví dụ: tây-bắc).
Do tính đơn giản của nó, mê cung tạo ra thường dễ giải hơn so với các thuật
toán khác và có tính bất đối xứng cao.
2.2.5. Thuật toán Aldous-Broder có độ lệch (Biased Aldous-Broder):
Nguyên lý hoạt động: Thuật toán Aldous-Broder bắt đầu tại một ô ngẫu
nhiên và thực hiện một bước đi ngẫu nhiên đến một ô lân cận chưa duyệt.
Nếu ô lân cận chưa được duyệt, bức tường giữa ô hiện tại và ô lân cận sẽ
bị "đục thủng". Quá trình này lặp lại cho đến khi tất cả các ô đều đã được
duyệt. Phiên bản "biased" của thuật toán này giới thiệu một xác suất ưu tiên
cho việc di chuyển theo một hướng cụ thể (trong trường hợp của nhóm,
hướng ngang), ảnh hưởng đến hình dạng tổng thể của mê cung. Đặc điểm
mê cung: Thuật toán Aldous-Broder tạo ra các mê cung có xu hướng đồng
đều hơn và ít đường cụt hơn so với thuật toán Backtracking. Việc thêm độ
lệch (bias) sẽ làm cho mê cung có xu hướng phát triển nhiều hơn theo
hướng được ưu tiên (ví dụ: nhiều hành lang ngang hơn nếu độ lệch ngang cao).
Việc sử dụng nhiều thuật toán sinh mê cung khác nhau cho phép nhóm đánh
giá khả năng thích ứng và hiệu suất của các thuật toán tìm đường đã triển
khai trên các loại môi trường có cấu trúc và độ khó khác nhau. Bằng cách
so sánh hiệu suất của cùng một thuật toán tìm đường trên các mê cung được