Nghiên cứu và cài đặt bộ gán nhãn từ loại cho song ngữ Anh-Việt

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

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

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

3MỘ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

2MÔ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

Nghiên cứu planning đểgiải bài toán xác định lộtrình

7

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

1GIẢ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

2GIỚ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

Nghiên cứu planning đểgiải bài toán xác định lộtrình

8

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

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

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

3LẬ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

1MÔ TẢ. 88

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

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

Nghiên cứu planning đểgiải bài toán xác định lộtrình

9

2VÍ 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

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

2ÝTƯỞNG. 115

3CÀI ĐẶT AGENT . 116

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

5KẾ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

Nghiên cứu planning đểgiải bài toán xác định lộtrình

10

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

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

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

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

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

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