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

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