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 . 14