BÁO CÁO GAME GIẢ I MÊ CUNG SỬ DỤNG A*

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (436.54 KB, 11 trang )

Trang 1<div class="page_container" data-page="1">

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

BÁO CÁO

GAME GIẢI MÊ CUNG SỬ DỤNG A*

HÀ NỘI, 2023

</div>Trang 2<div class="page_container" data-page="2">

MỤC LỤC

LỜI NÓI ĐẦU

...

3 1. Tổng quan

. ...

4

1.1. Đặt vấn đề. ... 4

1.2. Giải thuật tìm kiếm. ... 4

1.3. Tổng quan về các giải thuật tìm kiếm. ... 4

2. Phương pháp giải quyết bài toán

. ...

5

2.1. Lịch sử của A* ... 5

2.2. Ý tưởng giải quyết bài toán. ... 5

2.3. Đánh giá giải thuật A* ... 9

3. Các khó khăn gặp phải và cách khắc phục

. ...

10 4. Đề xuất phương pháp cải tiến giải thuật A*

. ...

10 5. Tổng kết

. ...

10 6. Tài liệu tham khảo

. ...

11

</div>Trang 3<div class="page_container" data-page="3">

LỜI NÓI ĐẦU

Lời đầu tiên nhóm em xin được gửi lời cảm ơn tới thầy Thân Quang Khoát đã thực hiện giảng dạy môn học nhập môn AI. Sau khi hoàn thành môn học bọn em đã thu được thêm rất nhiều kiến thức mới bổ ích. Trong đó nhóm em thực sự tâm đắc với phần các thuật toán tìm kiếm và quyết định thực hiện một đề tài với chủ đề là: thực hiện game giải mê cung sử dụng thuật tốn tìm đường A*. Đây là mợt thuật tốn tìm kiếm thõa mãn ràng ḅc

Lý do chọn đề tài này của nhóm em đó là vì đây là mợt đề rất thú vị, có tính ứng dụng cao trong thực tiễn. Có thể giúp chúng ta tìm được đường đi một cách tối ưu trong việc xây dựng bản đồ các tuyến đường hay trong các lĩnh vực lĩnh vực trí tuệ nhân tạo, các hệ thống xe tự hành,…

</div>Trang 4<div class="page_container" data-page="4">

1. Tổng quan.

1.1. Đặt vấn đề.

Sử dụng các giải thuật tìm kiếm A* để tìm đường đi tới ưu nhất giữa hai điểm bắt đầu và đích đến đã biết trong mê cung. Trong đó mê cung sẽ có các lối đi và tường là phần không đi được, điểm bắt đầu và đích đến sẽ được tạo mới mợt cách ngẫu nhiên.

1.2. Giải thuật tìm kiếm.

Định nghĩa thuật toán tìm kiếm: Trong ngành khoa học máy tính, mợt giải thuật tìm

kiếm là mợt thuật tốn lấy đầu vào là mợt bài tốn và trả về kết quả là một lời giải cho bài tốn đó, thường là sau khi cân nhắc giữa mợt loạt các lời giải có thể. Hầu hết các thuật toán được nghiên cứu bởi các nhà khoa học máy tính để giải quyết các bài toán đều là các thuật tốn tìm kiếm. Tập hợp tất cả các lời giải có thể đới với mợt bài tốn được gọi là khơng gian tìm kiếm. Thuật toán thử sai (brute-force search) hay các thuật tốn tìm kiếm "sơ đẳng" khơng có thơng tin sử dụng phương pháp đơn giản nhất và trực quan nhất. Trong khi đó, các thuật tốn tìm kiếm có thơng tin sử dụng heuristics để áp dụng các tri thức về cấu trúc của không gian tìm kiếm nhằm giảm thời gian cần thiết cho việc tìm kiếm.

Chúng ta đã được học rất nhiều loại giải thuật tìm kiếm như là tìm kiếm trên cây, tìm kiếm trên đờ thị, tìm kiếm đới kháng, tìm kiếm thỏa mãn ràng ḅc,…

Trong q trình học ta đã được học với mợt sớ giải thuật tìm kiếm cơ bản trong đồ thị cơ bản như: BFS, UCS, DFS, DLS, IDS.

Hay các giải thuật tìm kiếm với tri thức bổ sung: best-first search, A*, giải thuật tìm kiếm thỏa mãn mợt ràng ḅc cho trước chằng hạn.

1.3. Tổng quan về các giải thuật tìm kiếm.

Đới với các giải thuật tìm kiếm cơ bản thì ta sẽ thực hiện bằng việc xây dựng các nút từ nút gốc và tìm ra nút đích của bài toán.

BFS (giải thuật tìm kiếm theo chiều rộng) chúng ta sẽ tiến hành phát triển các nút

bắt đầu từ nút gốc theo chiều rộng và thứ tự độ sâu tăng dần. Chúng ta sẽ ghé qua tất cả các nút hoặc cho tới khi tìm được nút đích. Tuy nhiên thuật toán này quá phức tạp về mặt thời gian và bợ nhớ dù nó có thể có tính hồn chỉnh.

UCS (giải thuật tìm kiếm với chi phí cực tiểu) ta tiến hành phát triển các nút có chi

phí thấp nhất (với chi phí từ nút gốc tới nút đang xét là tăng dần) đảm bảo tính hồn chỉnh, thời giản và bợ nhớ phụ thuộc vào tổng số nút có chi phí <= chi phí của lời giải tối ưu.

DFS (giải thuật tìm kiếm theo chiều sâu) ta phát triển các nút theo chiều sâu của

cây với cấu trúc LIFO (Last In First Out) tức là nút nào vào trước thì ở đợ sâu tiếp theo ta sẽ xét nhánh đó. Ta sẽ tập trung xét theo một nhánh cho tới khi tìm được đích hoặc đi mãi và không bao giờ tìm được nếu cây có đợ sâu vơ hạn. Nếu gặp đường cụt thì ta sẽ quay lại và xét nhánh khác.

Tính hồn chỉnh của giải thuật này là khơng có, thời gian tìm kiếm thì có thể rất lâu và tớn rất nhiều bợ nhớ. Khơng có tính tới ưu.

IDS (giải thuật tìm kiếm sâu dần)

Đối với giải thuật này ta vẫn áp dụng giải thuật tìm kiếm theo chiều sâu tuy nhiên tại mỗi bước ta sẽ giới hạn độ sâu cho nó sau đó phát triển các nút tại đơ sâu giới hạn đó,

</div>Trang 5<div class="page_container" data-page="5">

nếu như khơng tìm được kết quả ta sẽ tăng giới hạn độ sâu lên cứ như vậy cho tới khi tìm ra kết quả.

Giải thuật này đảm bảo tính hồn chỉnh, tiết kiệm thời gian cũng như bợ nhớ. Đây là một giải thuật tối ưu nếu cho phí cho mỗi bước đi đều bằng mợt.

Các giải thuật tìm kiếm với tri thức bổ sung: các giải thuật này hiệu quả hơn các giải thuật tìm kiếm cơ bản và có tính ứng dụng cao trong thực tiễn. Phải kể đến như là greedy best first search hay A*.

Đối với greedy best first search thì ý tưởng là sử dụng thêm một hàm đánh giá h(n)

cho mỗi nút cây tìm kiếm, hàm đánh giá được sử dụng ở đây là hàm heuristic. Heuristic là hàm dùng để đánh giá chi phí từ nút hiện tại đang đứng tới nút đích. Tập trung vào phát triển các nút có vẻ gần với nút mục tiêu nhất.

Giải thuật này không đảm bảo tính hồn chỉnh, độ phức tạp về thời gian và tốn bộ nhớ, không mang lại sự tới ưu.

Đối vói A* đây là giải thuật tốt hơn của giải thuật best first search, thay vì chỉ dùng có

1 hàm h(n) thì giờ đây ta dùng thêm mợt hàm f(n) tính tốn chi phí từ nút gớc đến nút hiện tại đang đứng. Ta sẽ lựa chọn đi các nút mà có f(n) + g(n) là nhỏ nhất.

2. Phương pháp giải quyết bài toán.

Để giải quyết bài tốn này thì chúng ta sẽ sử dụng giải thuật tìm kiếm A* để tìm đường đi ngắn nhất giữa hai điểm bắt đầu và đích đến cho trước.

Trước khi đi vào giải quyết bài toán chúng ta sẽ tìm hiểu xem A* là gì và nó có gì đặc biệt để có thể giải quyết bài toán này.

2.1. Lịch sử của A*

Thuật tốn A* được mơ tả lần đầu vào năm 1968 bởi Peter Hart, Nils Nilsson và Bertram Raphael. Trong bài báo của họ, thuật toán được gọi là A* khi sử dụng thuật tốn này đới với mợt đánh giá heuristic thích hợp sẽ thu được hoạt đợng tới ư, do đó mà có tên A*.

Năm 1964, Nils Nilsson phát minh ra một phương pháp tiếp cận dựa trên khám phá để tăng tớc đợ của thuật tốn Dijkstra. Thuật toán này được gọi là A1.

Năm 1967, Bertram Raphael đã cải thiện tốc độ của thuật tốn này nhưng khơng thể tới ưu được nó. Ơng gọi thuật tốn này là A2. Sau đó năm 1968 Peter E.Hart đã giới thiệu một đối số chứng minh A2 là tối ưu khi sử dụng thuật tốn này với mợt đánh giá heuristic thích hợp sẽ thu được hoạt động tối ưu.

Chứng minh của ông về thuật tốn này cũng bao gờm một phần cho thấy rằng các thuật tốn A2 mới là thuật tốn tớt nhất có thể được đưa ra các điều kiện. Do đó ơng đặt tên cho thuật tốn mới là thuật toán A*.

A* ban đầu là thuật toán tìm đường đi có chi phí thấp nhất khi mà chi phí của đường đi bằng tổng các chi phí của nó. Tuy nhiên người ta đã chứng minh là sẽ tìm được đường đi tối ưu cho bất kỳ bài tốn nào nếu như nó thỏa mãn ràng ḅc về chi phí.

2.2. Ý tưởng giải quyết bài toán.

Xét bài toán tìm đường, bài toán mà A* thường được dùng để giải. A* được xây dựng tăng dần tất cả các tuyến đường từ điểm x́t phát cho tới khi nó tìm thấy được một đường đi chạm tới đích. Tuy nhiên cũng như các thuật tốn tìm kiếm khác đó là nó lại chỉ tìm các đường đi vơ cớ dẫn về đích.

</div>Trang 6<div class="page_container" data-page="6">

Thuật tốn này sử dụng mợt đánh giá heuristic để sắp xếp các nút theo ước lượng về tuyến đường tớt nhất đo qua nút đó. Nó sẽ duyệt các nút đã sắp xếp và quyết định xem nút tiếp theo nó sẽ đi qua là nút nào.

Ta sẽ có f(n) = g(n) + h(n). (1)

Trong đó thì g(n) là khoảng cách từ nút hiện tại đang đứng tới nút đích, và h(n) là ước lượng theo đường chim bay khoảng cách từ nút hiện tại đang đứng tới đích. Có rất nhiều cách để tính toán h(n), ở đây ta sẽ sử dụng khoảng cách Manhattan để tính toán khoảng cách h(n).

Khoảng cách Manhattan còn được gọi là khoảng cách 𝐿1 hay khoảng cách trong thành phố, là một dạng khoảng cách giữa hai điểm trong không gian Euclid với hệ tọa độ Descartes. Đại lượng này được tính bằng tổng chiều dài của hình chiếu của đường thẳng nối hai điểm này trong hệ trục tọa đợ Descartes.

Ta có khoảng cách Manhattan giữa hai điểm 𝑃1(𝑥1, 𝑥2) và 𝑃2(𝑥2, 𝑦2) là |𝑥1− 𝑥2| + |𝑦1− 𝑦2|.

Nếu như mà f(n) đánh giá nút nào là bé nhất thì sẽ đi theo nút đó.

Điều này khác biệt với các thuật toán tìm đường khác khiến cho A* trở nên đầy đủ và tới ưu. Nó sẽ hoàn toàn tìm được đường đi ngắn nhất nếu tồn tại một đường đi như thế. Tuy nhiên A* sẽ không đảm bảo sẽ chạy nhanh hơn các thuật tốn tìm kiếm khác.

Ta có thể hiểu ý tưởng thuật tốn này thơng qua ví dụ dưới đây:

Hình 1: bản đồ thành phố

</div>Trang 7<div class="page_container" data-page="7">

Bảng 1: tên các thành phố và ước lượng khoảng cách đến đích tương ứng

Yêu cầu bài toán: hãy sử dụng A* để tìm đường đi ngắn nhất từ thành phố Arad đến Bucharest.

Lời giải:

Bước 1: xuất phát từ nút đầu tiên, dựa vào bảng 1 ta có chi phí ước lượng từ điểm bắt đầu tới đích cần đến h(n) của Arad là 366 và g(n) = 0 do ta bắt đầu xuất phát từ thành

phố Arad. Từ (1) ta sẽ tính ra f(n) = 0 + 366 = 366.

Hình 2: thực hiện giải thuật tìm đường A* bước một.

Bước 2: từ thành phố Arad ta sẽ có thể đi tới ba thành phố là Sibiu, Timisoara và Zerind. Ta sẽ dựa vào bảng lấy ra giá trị ước lượng h(n) và nhìn từ hình 1 ta sẽ thấy khoảng cách từ thành phố bắt đầu tới thành phố hiện tại đang đứng đặt là g(n), ta sẽ tính ra được f(n). Nếu f(n) của thành phố nào là nhỏ nhất thì ta sẽ chọn đi qua thành phớ đó.

Hình 3: thực hiện giải thuật tìm đường A* bước hai.

</div>Trang 8<div class="page_container" data-page="8">

Hình 4: thực hiện giải thuật tìm đường A* bước ba.

Hình 5: thực hiện giải thuật tìm đường A* bước bốn

Hình 6: thực hiện giải thuật tìm đường A* bước năm

Hình 7: tìm được đích cần đến

</div>Trang 9<div class="page_container" data-page="9">

Thực hiện tương tự như bước 2 cuối cùng chúng ta sẽ thu được chi phí đường đi ngắn nhất từ Arad đến Bucharest là 418 và truy vết ngược trở lại các nút chúng ta đã đi qua sẽ tìm được đường đi tối ưu nhất đến đích.

Với bài toán thực tế đặt ra chúng ta sẽ khởi tạo một ma trận kích thước 10x10. Các điểm bắt đầu và điểm kết thúc được khởi tạo một cách ngẫu nhiên sau mỗi lần ta chạy lại chương trình. Ma trận này sẽ có các đường đi và tường là những ô không thể đi qua được. Nhiệm vụ của chúng ta đó là sử dụng A* để tìm đường đi tối ưu đến đích. Chúng ta sẽ thực hiện như sau:

1. xác định điểm bắt đầu và điểm kết thúc.

2. khởi tạo một hàng đợi ưu tiên, thêm điểm bắt đầu và điểm kết thúc bằng hàm chi phí.

3. lặp lại các bước phía dưới cho đến khi tìm thấy đường đi tới ưu: 3.1. lấy ra nút có chi phí dự đốn thấp nhất khỏi hàng đợi

3.2. kiểm tra xem nút này có phải điểm kết thúc hay khơng. Nếu có, đường đi này là tối ưu

3.3. nếu không, tạo ra các nút con từ nút hiện tại và tính tốn từ điểm bất kỳ đến nút con và chi phí dự đốn từ nút con đến điểm kết thức bằng hàm chi phí.

3.4. thêm các nút con vào hàng đợi ưu tiên và cập nhật thơng tin nếu chi phí dự đốn thấp hơn nút đã có trong hàng đợi.

4. nếu khơng tìm thấy đường đi tới điểm kết thúc thì ta kết luận khơng tờn tại đường đi tới địch.

5. truy vết đường đi tối ưu từ điểm kết thúc tới điểm bắt đầu bằng các nút đã được lưu lại trong quá trình tìm kiếm.

2.3. Đánh giá giải thuật A*

Nếu không gian trạng thái là hữu hạn và tránh được việc mắc vào các vịng lặp trạng thái thì giải thuật A* có tính hồn chỉnh tuy nhiên khơng dám đảm bảo tính tới ưu. Nếu ta không thể tránh được việc lặp trạng thái hoặc không gian trạng thái không hữu hạn thì giải thuật này khơng có tính hồn chỉnh.

Giải thuật A* có tính tới ưu nếu nó có thể tho mãn hàm heuristic là một ước lượng chấp nhận được.

Hàm heuristic h*(n) thỏa mãn ước lượng chấp nhận được nếu 0 =< h*(n) <= h(n), trong đó h(n) là chi phí thực tế để đi từ nút hiện tại đang xét tới nút đích.

Tính nhất quán trong giải thuật A*

Nếu heuristic h(x) được coi là nhất quán đơn điệu nếu thỏa mãn điều kiện bổ sung: h(x) =< d(x, y) + h(y).

Trong đó:

- x là điểm ta đang xét. - y là mọi điểm lân cận với x. - d(x, y) là chi phí đi từ x tới y.

Tức là đối với mọi điểm x và mỗi điểm lân cận y kế tiếp của x thì chi phí ước tính để đến được đích từ x không lớn hơn chi phí đi từ x tới y cộng với chi phí ước tính để đến đích từ y.

Khi đó A* được đảm bảo tìm ra đường đi tối ưu không cần xử lý bất kỳ nút nào nhiều hơn một lần. Nghĩa là trong trường hợp hàm đánh giá là có thể chấp nhận được nhưng

</div>Trang 10<div class="page_container" data-page="10">

lại khơng nhất qn, thì tại mợt điểm sẽ bị mở rộng lặp lại tại mỗi khi tìm được đường đi có chi phí tớt hơn.

3. Các khó khăn gặp phải và cách khắc phục.

A* tuy là một trong những giải thuật tìm đường phổ biến và hiệu quả nhất tuy nhiên khi xây dựng A* chúng ta vẫn gặp phải một sớ khó khăn như là:

- nếu chúng ta dự đốn hàm heuristic sai, thiếu thơng tin có thể dẫn đến tìm đường sai - quá tốn bộ nhớ, thời gian thực thi lâu: nếu như xây dựng mê cung quá lớn, nhiều nút dẫn đến phức tạp, ảnh hưởng hiệu suất.

- do điếm bắt đầu và đích đến được khởi tạo ngẫu nhiên do đó có thể khơng tìm được đích đến: trong trường hợp không tồn tại đường đi từ điểm bắt đầu đến đích.

- trường hợp gặp phải các vòng lặp có thể khơng thể thốt ra được dẫn đến không tìm được đường đi đến đích.

4. Đề xuất phương pháp cải tiến giải thuật A*.

Các giải thuật cải tiến của A* mà ta có thể nghĩ đến là kết hợp giữa A* và DFS tạo ra thuật toán tìm đường mới là IDA*. Được sử dụng trong trường hợp không gian trạng thái của chúng ta là lớn và khơng có thơng tin chi phí chính xác Thuật toán này cho phép ta tìm kiếm đường đi theo từng độ sâu ngày càng tăng cho đến khi tìm thấy đích. Trong giải thuật này chúng ta cần đặt giới hạn (threshold) ban đầu bằng giá trị ước tính heuristic từ trạng thái bắt đầu tới trạng thái đích.

Sử dụng tìm kiếm theo chiều sâu, thực hiện mợt lần tìm kiếm từ trạng thái bắt đầu với giới hạn (threshold) đã đặt. Trong quá trình tìm kiếm, IDA* theo dõi giá trị chi phí tới trạng thái hiện tại (thường là tổng các giá trị heuristic đã xem xét) và so sánh với giới hạn. Nếu chi phí vượt quá giới hạn, thuật toán sẽ dừng tìm kiếm tại đây.

Nếu đích được tìm thấy, thuật toán kết thúc và trả về giải pháp tìm được.

Nếu khơng tìm thấy đích trong mợt lần tìm kiếm theo chiều sâu giới hạn, tăng giới hạn bằng giá trị heuristic nhỏ nhất của các trạng thái khơng thể duyệt qua trong lần tìm kiếm trước đó.

Tiếp tục lặp lại các bước sử dụng tìm kiếm theo chiều sâu và theo dõi giá trị chi phí cho tới khi tìm ra được đường đi tối ưu hoặc không còn trạng thái để duyệt.

Ngoài ra ta có thể áp dụng phương pháp cắt tỉa alpha – beta để cắt tỉa đi các nhánh mà ta cảm thấy k có tiềm năng hay không thể tìm được đường đi đến đích để giảm thiểu bộ nhớ và thời gian thực hiện.

Ở đây ta còn sử dụng hàm heuristic thông minh tính bằng khoảng cách Manhattan để ước lượng chính xác chi phí đi từ nút hiện tại tới đích thay vì ước lượng một cách ngẫu nhiên. Giúp tối ưu được rất nhiều cho bài tốn đảm bảo tính tới ưu và tiết kiệm được rất nhiều thời gian tìm kiếm.

5. Tổng kết.

Thực hiện đề tài này đã giúp nhóm em tự mình giải quyết được bài tốn thực tế tìm kiếm đường đi trong mê cung với chi phí nhỏ nhất giữa hai điểm ta đã biết. Nếu rộng ra là ta sẽ có thể ứng dụng được trong việc xác định được các tuyến đường tốt nhất để đi trên bản đồ khi biết điểm bắt đầu và điểm kết thúc, hay tìm đường đi cho robot vượt chướng ngại vật và tìm đường về đích nhanh nhất,…

Qua đây chúng em đã học được thêm rất nhiều kiến thức để phục vụ cho việc học tập và công việc sau này.

</div>