[FONT=Times New Roman]Lời mở đầu

Từ trước đến nay có rất nhiều bài toán được đặt ra, cần nghiên cứu cách

giải quyết. Những bài toán khó nhất vẫn là những bài toán thực tế của

cuộc sống. Với sự phát triển mạnh mẽ của Công nghệ thông tin như hiện

nay, các bài toán thường được đưa vào máy tính để xử lí. Đa số các bài

toán được giải quyết bằng cách áp dụng trí thông minh nhân tạo

(Artificial Intelligent (AI)). Thuật ngữ “planning” được sử dụng trong AI

khi bài toán là bài toán thế giới thực được gọi là AI planning. Con người

thường có thói quen dự định một việc gì đó trước khi làm và hầu như con

người biết có những hành động nào để đạt được những dự định đó. Để

giúp máy tính làm việc như con người, nghĩa là biết những hành động

nào có thể đi đến mục tiêu, ta cần cung cấp tri thức cho nó. Tri thức ở đây

rất đa dạng, để máy tính “hiểu” được môi trường xung quanh nó như thế

nào là việc rất khó khăn. Một máy tính có những trang thiết bị hiện đại

nhất vẫn không thể cảm nhận hết những thay đổi của môi trường. Tuy

nhiên, đối với một bài toán cụ thể nào đó, máy tính chỉ cần ghi nhận

những tri thức liên quan. Với những tri thức đó bộ lập kế hoạch sẽ giúp

máy tính biết cần hành động thế nào để đạt được mục tiêu bằng cách đưa

ra những kế hoạch tương ứng lấy từ tri thức sẵn có. Trong lĩnh vực AI,

lập kế hoạch là vấn đề khá mới so với nhận dạng, xử lí ảnh, xử lí ngôn

ngữ, xử lí âm thanh,…đã được nghiên cứu rất nhiều. Nhưng lập kế hoạch

có sức mạnh rất lớn trong việc tiếp cận và giải quyết những vấn đề thực tế

trong cuộc sống như: chế tạo robot làm việc nhà: biết đi chợ, quét dọn

nhà cửa,…; robot tự động làm việc ở những vị trí khá nguy hiểm cho con

người như nhà cao tầng hay ngoài không gian,…Một sức mạnh khác của

lập kế hoạch tạo ra những robot có thể phản ứng với những biến đổi bất

thường của môi trường. Vì trong tự nhiên, chỉ có những động thực vật

mới có thể làm điều này. Trong luận văn này, lập kế hoạch được sử dụng

để giải quyết bài toán xác định lộ trình trong thành phố Hồ Chí Minh. Với

các tri thức cần cập nhật như luật đi đường, xuất hiện các sự cố gây tắt

nghẽn giao thông ở đoạn đường nào, các trường học, bệnh viện, nhà thờ,

trụ sở nhà nước, cây xăng, sân vận động, rạp chiếu phim,… được đặt tại

đâu. Bộ lập kế hoạch có thể giúp tìm ra những con đường tốt nhất về thời

gian, tốc độ, nhiên liệu,…để đến mục tiêu với tri thức được cập nhật

thường xuyên.

MỤC LỤC

PHẦN I: CƠ SỞ LÝ THUYẾT TRONG LẬP KẾ HOẠCH............................ 11

lịch sử lập kế hoạch .................................................. ....................................... 12

CHƯƠNG 1:CÁC KHÁI NIỆM CƠ BẢN............................................. .......... 16

1 CÁC THUẬT NGỮ CHUNG TRONG LẬP KẾ HOẠCH...................... 16

2 BẢN CHẤT CỦA VẦN ĐỀ LẬP KẾ HOẠCH....................................... 18

3 MỘT SỐ ỨNG DỤNG CỦA LẬP KẾ HOẠCH TRONG THỰC TẾ..... 19

3.1. Robot sắp xếp các khối .................................................. ....................... 19

3.2. Robot mua hàng hoá .................................................. ........................... 20

CHƯƠNG 2:CÁC ĐỐI TƯỢNG TRONG LẬP KẾ HOẠCH......................... 22

1 AGENT .................................................. .................................................. . 22

1.1. Khái niệm............................................ .................................................. 22

1.2. Hành động của agent............................................. ................................ 23

1.3. Agent program .................................................. .................................... 26

1.4. Các yếu tố để xây dựng agent program........................................... ...... 28

1.5. Cấu trúc agent .................................................. ..................................... 29

1.6. Các loại agent............................................. ........................................... 30

1.6.1. Agent phản xạ đơn giản .................................................. ...................... 30

1.6.2. Agent lưu vết môi trường......................................... ............................. 32

1.6.3. Agent dựa trên mục tiêu............................................. ........................... 34

1.6.4. Agent dựa trên tính hiệu quả............................................. .................... 35

2 MÔI TRƯỜNG .................................................. ....................................... 37

2.1. Khái niệm............................................ .................................................. 37

2.2. Các loại môi trường và thuộc tính của nó ............................................. 38

2.2.1. Môi trường tiếp cận được và không tiếp cận được ............................... 38

2.2.2. Môi trường xác định và không xác định ............................................... 38

2.2.3. Môi trường episodic và nonepisodic....................................... .............. 38

2.2.4. Môi trường tĩnh và động .................................................. ..................... 39

2.2.5. Môi trường rời rạc và liên tục .................................................. ............. 39

CHƯƠNG 3:CÁC LÝ THUYẾT LIÊN QUAN ĐẾN LẬP KẾ HOẠCH........ 42

1 GIẢI TOÁN BẰNG PHƯƠNG PHÁP TÌM KIẾM................................. 42

1.1. Agent giải quyết bài toán .................................................. .................... 42

1.1.1. Mô tả .................................................. .................................................. . 42

1.1.2. Ví dụ.............................................. .................................................. ...... 43

1.1.3. Chương trình agent giải quyết bài toán đơn giản.................................. 43

1.2. Thiết lập bài toán............................................. ...................................... 44

1.2.1. Các kiểu bài toán .................................................. ................................. 45

1.2.1.1. Bài toán trạng thái đơn .................................................. .................... 45

1.2.1.2. Bài toán đa trạng thái .................................................. ...................... 46

1.2.1.3. Bài toán ngẫu nhiên............................................ ............................... 46

1.2.1.4. Bài toán khảo sát .................................................. ............................. 47

1.2.2. Định nghĩa bài toán và giải pháp .................................................. ........ 47

1.2.3. Đo mức độ thực thi của việc giải toán .................................................. 48

1.2.3.1. Các phương pháp đo độ thực thi .................................................. ..... 48

1.2.3.2. Ví dụ.............................................. .................................................. .. 49

1.2.4. Chọn trạng thái và hành động .................................................. ............. 49

1.3. Tìm kiếm giải pháp .................................................. ............................. 51

1.3.1. Tạo các chuỗi hành động .................................................. .................... 51

1.3.2. Cấu trúc dữ liệu của cây tìm kiếm .................................................. ...... 54

2 GIỚI THIỆU ngôn ngữ MÔ TẢ BÀI TOÁN..................................... 56

2.1. Sự trình bày, suy luận và logic............................................. ................. 57

2.1.1. Sự trình bày ngôn ngữ............................................. .............................. 57

2.1.2. Suy luận............................................ .................................................. ... 59

2.2. Logic mệnh đề............................................. .......................................... 60

2.2.1. Cú pháp .................................................. ............................................... 60

2.2.2. Ngữ nghĩa............................................ .................................................. 61

2.3. Logic trật tự đầu tiên .................................................. ........................... 61

2.3.1. Cú pháp và ngữ nghĩa .................................................. ......................... 62

2.3.2. Các ví dụ .................................................. ............................................. 63

2.3.3. Lượng từ.............................................. .................................................. 64

2.3.4. Những ký hiệu đặt biệt trong tập hợp, danh sách và số học ................. 65

2.3.5. Phép tính tình huống .................................................. ........................... 66

CHƯƠNG 4:CÁC VẤN ĐỀ TRONG LẬP KẾ HOẠCH ................................ 69

1 GIỚI THIỆU AGENT LẬP KẾ HOẠCH ĐƠN GIẢN............................ 69

2 TỪ GIẢI QUYẾT BÀI TOÁN ĐẾN LẬP KẾ HOẠCH.......................... 70

3 LẬP KẾ HOẠCH SỬ DỤNG PHÉP TÍNH TÌNH HUỐNG ................... 75

4 ngôn ngữ STRIPS: NGÔN NGỮ TRÌNH BÀY CƠ BẢN TRONG

LẬP KẾ HOẠCH........................................... .................................................. . 77

4.1. Mô tả trạng thái và mục tiêu .................................................. ............... 77

4.2. Mô tả hành động .................................................. ................................. 78

4.3. Không gian ngữ cảnh và không gian kế hoạch ..................................... 80

4.4. Trình bày kế hoạch........................................... ..................................... 81

4.5. Giải pháp .................................................. ............................................. 85

CHƯƠNG 5:THUẬT TOÁN PARTIAL-ORDER-PLANNING (POP) .......... 88

1 MÔ TẢ.............................................. .................................................. ...... 88

1.1. Ý tưởng thuật toán............................................. .................................... 88

1.2. Chi tiết thuật toán .................................................. ................................ 89

2 VÍ DỤ.............................................. .................................................. ........ 90

2.1. Mô tả bài toán .................................................. ..................................... 90

2.2. Áp dụng thuật toán POP cho bài toán .................................................. . 91

CHƯƠNG 6:MÔ HÌNH LẬP KẾ HOẠCH PHÂN RÃ PHÂN CẤP ............ 100

1 PHÂN RÃ PHÂN CẤP TOÁN TỬ.............................................. .......... 100

1.1. Đặt vấn đề .................................................. ......................................... 100

1.2. Phân rã phân cấp là gì? .................................................. ..................... 100

1.3. Ví dụ.............................................. .................................................. .... 101

1.4. Các vấn đề cần quan tâm đối với lập kế hoạch phân rã phân cấp....... 102

1.4.1. Mở rộng ngôn ngữ STRIPS .................................................. .............. 102

1.4.2. Thuật toán HD-POP .................................................. .......................... 103

2 PHÂN TÍCH MÔ HÌNH PHÂN RÃ PHÂN CẤP.................................. 106

2.1. Giải pháp thuận và giải pháp nghịch.......................................... ......... 107

2.2. Ví dụ.............................................. .................................................. .... 110

2.3. Sự phân rã và dùng chung .................................................. ................. 112

PHẦN 2:ỨNG DỤNG LẬP KẾ HOẠCH TRONG BÀI TOÁN TÌM ĐƯỜNG

ĐI............................................... .................................................. .................... 115

1 GIỚI THIỆU BÀI TOÁN .................................................. ..................... 115

2 Ý TƯỞNG.......................................... .................................................. ... 115

3 CÀI ĐẶT AGENT .................................................. ................................ 116

4 CÁC CHIẾN LƯỢC .................................................. ............................. 116

5 KẾT QUẢ THỰC NGHIỆM .................................................. ................ 119

5.1. Chiến lược 2 và bộ lập kế hoạch truy hồi ........................................... 125

5.2. Chiến lược 3 và bộ lập kế hoạch truy hồi ........................................... 131

6 SO SÁNH LẬP TRÌNH KẾ HOẠCH VÀ LẬP TRÌNH THEO LÝ

THUYẾT ĐỒ THỊ .................................................. ........................................ 136

6.1. Thuật toán DijkstraMoore..................................... .............................. 136

6.2. Đối với lập trình kế hoạch........................................... ........................ 136

PHẦN 3: TỔNG KẾT .................................................. ................................... 139

1 NHỮNG GÌ ĐÃ LÀM ĐƯỢC.......................................... ...................... 139

2 NHỮNG GÌ CHƯA LÀM ĐƯỢC.......................................... ................ 139

3 HƯỚNG PHÁT TRIỂN........................................... ............................... 140

TÀI LIỆU THAM KHẢO............................................ ................................... 141