TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN CÔNG NGHỆ TRI THỨC
LUẬN VĂN CỬ NHÂN TIN HỌC
NGHIÊN CỨU PLANNING
ĐỂ GIẢI BÀI TOÁN XÁC ĐỊNH LỘ TRÌNH
GVHD: Th.S. Nguyễn Phương Thảo
SVTH: Trần Thuỷ Tiên 9912704
Trần Hồng Thái 9912071
TP. HỒ CHÍ MINH, 2003
Nghiên cứu planning để giải bài toán xác định lộ trình
1
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,
động viên và giúp đỡ vượt qua những khó khăn để hoàn
thành luận văn này.
Đặt biệt, chúng con xin cảm ơn các bậc cha mẹ và
những người thân đã hết lòng nuôi nấn
g dạy dỗ để chúng
con có được ngày hôm nay.
Do còn hạn chế về nhiều mặt nên luận văn còn
nhiều thiếu sót, chúng em kính mong quý thầy cô cùng b
ạn
bè đóng góp ý kiến để chúng em có thể khắc phục, hoàn
thiện hơn.
Thành phố Hồ Chí Minh
Tháng 7 – 2003
Nghiên cứu planning để giải bài toán xác định lộ trình
4
NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
.......................................................................................................................
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.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
Lịch sử lập kế hoạch
Nguồn gốc của AI planning một phần xuất phát từ việc giải quyết bài
toán (problem solving) qua sự tìm kiếm trong không gian trạng thái và
những kỹ thuật phối hợp khác như suy diễn bài toán và sự phân tích
“means-ends”, đặt biệt được nhấn mạnh trong GPS (General Problem
Solver) của Newell và Simon (1961). Một phần xuất phát từ việc chứng
minh định lý và tính toán ngữ cảnh, AI planning được nhấn mạnh trong
hệ chứng minh định lý QA3 (Green, 1969). Sự ra đời của planning được
thúc đẩy bởi nhu cầu về robot.
Năm 1971, Fikes và Nilsson xây dựng hệ lập kế hoạch quan trọng
đầu tiên STRIPS mô tả sự tương tác của ba ảnh hưởng này. STRIPS được
thiết kế như thành phần lập kế hoạch của phần mềm cho dự án robot
Shakey ở Học viện nghiên cứu quốc tế Stanford (SRI). Cấu trúc điều
khiển toàn thể của nó được mô hình theo GPS và sử dụng QA3 như là thủ
tục con để thiếtlập điều kiện tiên quyết của hành động.
Năm 1986, Lifschitz đưa ra những phê bình chi tiết và sự phân tích
chính thức đối với hệ thống STRIPS.
Năm 1992, Bylander thể hiện việc lập kế hoạch đơn giản theo dạng
STRIPS, đó là PSPACE hoàn chỉnh.
Nghiên cứu planning để giải bài toán xác định lộ trình
13
Năm 1993, Fikes và Nilsson tiến hành triển lãm lịch sử trên dự án
STRIPS, và chỉ ra cái nhìn tổng quan về mối quan hệ của nó với những
kết quả lập kế hoạch gần đây.
Trong nhiều năm, sự lộn xộn của những thuật ngữ bao trùm lĩnh
vực lập kế hoạch:
• Năm 1987, Genesereth và Nilsson sử dụng thuật ngữ linear để chỉ
trật tự tổng thể và nonlinear chỉ trật tự cục bộ.
• Năm 1975, Sacerdoti sử dụng linear để chỉ thuộc tính mà ta gọi là
không thể xen kẻ. Với tập các mục tiêu con cho trước, bộ lập kế
về lập kế hoạch. Reading in Planning (Allen và những người khác, 1990)
là tập hợp nhiều bài báo tốt nhất trong lĩnh vực này. Planning and
Control (Dean và Wellman, 1991) là sách giáo khoa hay giới thiệu tổng
quát về lập kế hoạch, và điều đặt biệt chú ý ở đây là vì nó tạo ra một kết
quả đặt biệt để kết hợp những kỹ thuật AI planning cổ điển với lý thuyết
điều khiển cổ điển và hiện đại, sự suy luận, lập kế hoạch tương tác và
giám sát thực thi.
Năm 1994, Weld cung cấp cái nhìn đặt sắc về các thuật toán lập kế
hoạch hiện đại.
Nghiên cứu planning tập trung vào AI vì đây là điểm xuất phát của
nó, những bài báo về planning đóng vai trò chủ đạo trong những tạp san
và hội nghị AI, nhưng cũng có những hội nghị đặt biệt dành riêng cho
planning, như hội nghị Timberline, hội nghị DARPA, 1990 với những
tiếp cận mới như lập kế hoạch, lập lịch và điều khiểnhay những hội nghị
quốc tế về các hệ AI Planning.
Nghiên cứu planning để giải bài toán xác định lộ trình
15
CHƯƠNG 1:
CÁC KHÁI NIỆM CƠ BẢN
1. Các thuật ngữ chung trong lập kế hoạch
2. Bản chất của vấn đề lập kế hoạch
3. Một số ứng dụng của lập kế hoạch trong thực tế
Nghiên cứu planning để giải bài toán xác định lộ trình
16
CHƯƠNG 1:
CÁC KHÁI NIỆM CƠ BẢN
1CÁC THUẬT NGỮ CHUNG TRONG LẬP KẾ HOẠCH
Agent-Tác nhân
Là những gì nhận thức từ môi trường xung quanh qua cơ quan cảm giác
và phản ứng trở lại môi trường qua cơ quan phản ứng. Ví dụ: con người,
thường xuyên. Các kế hoạch trong thư viện thường có dạng If … then …
Nghiên cứu planning để giải bài toán xác định lộ trình
18
State space - Không gian trạng thái
Bao gồm những trạng thái có thể có của agent khi thực hiện hành động.
Đối với bài toán cụ thể, không gian trạng thái là hữu hạn.
Plan space - Không gian kế hoạch
Chứa những kế hoạch của agent. Không giống như thư viện kế hoạch,
không gian kế hoạch có thể trùng lắp. Vì thế không gian kế hoạch thường
vô hạn.
Solution - Giải pháp
Là những kế hoạch thu được mục tiêu.
Causal link - Liên kết nhân quả
Là những liên kết tất yếu, khi thực hiện hành động này chắc chắn thu
được trạng thái kia.
2BẢN CHẤT CỦA VẦN ĐỀ LẬP KẾ HOẠCH
Lập kế hoạch cũng là một cách tiếp cận để giải quyết bài toán như bao
cách tiếp cận khác. Tuy nhiên, điều khác biệt của lập kế hoạch so với
những cách tiếp cận đó là nó tạo ra một agent để xử lí và thực thi hành
động trong môi trường cụ thể của bài toán. Agent này có cơ quan cảm
giác để cảm nhận và cập nhật tri thức từ môi trường và có cơ quan phản
ứng để thực thi các hành động mà agent đưa ra. Điều quan trọng nhất
Nghiên cứu planning để giải bài toán xác định lộ trình
19
trong agent này là bộ lập kế hoạch, bộ lập kế hoạch tiếp nhận tri thức, xử
lí và đưa ra những kế hoạch phù hợp.
Trong luận văn này, do sự giới hạn về nhiều mặt, chúng tôi không
thể xây dựng các cơ quan cảm giác và cơ quan phản ứng, chỉ xây dựng bộ
lập kế hoạch tổng quát của agent.
3MỘT SỐ ỨNG DỤNG CỦA LẬP KẾ HOẠCH TRONG
HOẠCH
1. Agent
2. Môi trường
Nghiên cứu planning để giải bài toán xác định lộ trình
22
CHƯƠNG 2:
CÁC ĐỐI TƯỢNG TRONG LẬP KẾ
HOẠCH
1AGENT
1.1. Khái niệm
Agent là các vật có khả năng nhận thức được môi trường xung quanh nó
qua các cơ quan cảm giác và tác động lại môi trường qua các cơ quan
phản ứng.
Hình 2.1 thể hiện sự tương tác giữa agent và môi trường xung
quanh nó qua các cơ quan cảm giác và cơ quan phản ứng.
Ví dụ:
− Agent con người có mắt, tai và các cơ quan khác là cơ quan cảm
giác, còn tay, chân, miệng và các phần cơ thể khác là các cơ quan
phản ứng.
cơ quan vận động
môi
trường
→ ?
cơ quan cảm
iá
tri thức
hành động
Hình 2.1 agent tương tác với môi trường qua cơ quan cảm giác và cơ quan phản ứng
Nghiên cứu planning để giải bài toán xác định lộ trình
hiện hành động mà nó cho là đúng, dựa vào tác động của ngữ cảnh,
những kết quả có thể không như mong muốn.
Tóm lại, để biết một agent hoạt động tốt hay không ở một thời
điểm nào đó, ta dựa vào 4 yếu tố sau:
• Độ đo thực thi định nghĩa mức độ thành công.
• Tất cả mọi điều mà agent nhận thức được từ trước đến nay. Lịch
sử tri thức hoàn chỉnh này được gọi là chuỗi nhận thức.
• Những gì mà agent biết về môi trường.
• Những hành động mà agent có thể thực thi.
Một agent là một ánh xạ từ những chuỗi nhận thức sang các hành
động.
Giả sử rằng hành vi của agent chỉ phụ thuộc vào chuỗi nhận thức
của nó, thì bất kỳ một agent cụ thể nào cũng có thể được mô tả bằng một
bảng gồm các hành động tương ứng với mỗi chuỗi nhận thức. (Đối với
hầuhết các agent, bảng này gồm một danh sách rất dài – vô hạn, trừ khi
nó được giới hạn chiều dài của chuỗi nhận thức được xem xét.) Danh
sách này được gọi là một ánh xạ từ các chuỗi nhận thức sang các hành
động. Nói chung, chúng ta có thể tìm thấy ánh xạ mô tả chính xác agent
bằng cách thử tất cả các chuỗi nhậnthức và ghi lại các hành động tương
ứng mà agent thực hiện. (Nếu agent sử dụng các giá trị ngẫu nhiên, thì
phải thử những chuỗi nhận thức vài lần để lấy giá trị trung bình về hành
vi của agent.). Một ánh xạ thể hiệnmột agent và ánh xạ lí tưởng sẽ thể
hiện agent lí tưởng. Để thiết kế agent lí tưởng cần xác định những hành
động mà agent phải thực hiện dựa trên chuỗi tri thức đã có.
Tuy nhiên, không nhất thiết phải tạo một bảng chi tiết cho mọi
chuỗi nhận thức. Ta có thể định nghĩa một ánh xạ cụ thể mà không cần
phải liệt kê tường tận nó. Xét ví dụ sau: một agent đơn giản là hàm tính
Copyright: Tài liệu đại học ©