Luận Văn Tìm hiểu 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
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
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
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
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
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 .