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,

ọ
c
Khoa Học Tự Nhiên đã tận tình chỉ bảo, tru
y
ền đ
ạ
t nhữn
g
kiến thức quý báo để chúng em làm hành trang vào đời.
Chúng em xin chân thành cảm ơn tất cả bạn bè đã
độ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ún
g
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
Nghiên cứu planning để giải bài toán xác định lộ trình
5
NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN


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

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

CHƯƠNG 2:
CÁC ĐỐI TƯỢNG TRONG LẬP KẾ HOẠCH
CHƯƠNG 3:
CÁC LÝ THUYẾT LIÊN QUAN ĐẾN LẬP KẾ HOẠCH
CHƯƠNG 4:
CÁC VẤN ĐỀ TRONG LẬP KẾ HOẠCH
CHƯƠNG 5:
THUẬT TOÁN PARTIAL-ORDER-PLANNING (POP)
CHƯƠNG 6:
MÔ HÌNH LẬP KẾ HOẠCH PHÂN RÃ PHÂN CẤP
Nghiên cứu planning để giải bài toán xác định lộ trình
12
PHẦN I:
CƠ SỞ LÝ THUYẾT TRONG LẬP
KẾ HOẠCH
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.

phong trong việc xây dựng những kế hoạch trật tự cục bộ, và nó được
khai thác kỹ lưỡng trong hệ NONLIN của Tate (1977), và giữ lại cấu trúc
khái niệm của bộ lập kế hoạch INTERPLAN. NONLIN cũng là bộ lập kế
Nghiên cứu planning để giải bài toán xác định lộ trình
14
hoạch đầu tiên sử dụng thuật toán rõ ràng để xác định những điều kiện
đúng sai ở những điểm khác nhau trong kế hoạch cục bộ.
Năm 1987, Chapman đưa ra TWEAK chính thức là hệ lập kế hoạch
thứ tự cục bộ. Chapman cung cấp sự phân tích chi tiết, bao gồm việc
chứng minh tính hoàn chỉnh và khó khăn của việc thiết lập những bài
toán lập kế hoạch khác nhau và các thành phần con của nó. Thuật toán
POP sử dụng trong luận văn này dựa trên thuật toán SNLP do Soderland
và Weld đưa ra năm 1991, thuật toán này là một cài đặt của bộ lập kế
hoạch mô tả bởi McAllester và Rosenblitt năm 1991.
Năm 1986, tại hội thảo Timberline đã trình bày những bài báo quan trọng
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.

Đoạn chương trình cụ thể cài đặt cho một agent cụ thể
Environment - Môi trường
Là tất cả những gì xung quanh agent, cung cấp tri thức cho agent và nhận
những phản ứng của agent.
World state - Trạng thái môi trường
Trạng thái môi trường xung quanh agent được xác định trong những thời
điểm cụ thể.
Plan - Kế hoạch
Là chuỗi hành động do agent tạo ra và được thực thi bởi agent.
Operator - Toán tử
Tập các ký hiệu mô tả hành động của agent, đồng thời mô tả các điều
kiện và kết quả của hành động.
Plan library - Thư viện kế hoạch
Tập luật về các hành động của agent, đây là tập các kế hoạch, thư viện
tuy không đầy đủ tất cả các kế hoạch nhưng thư viện này có thể cập nhật
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.

Kế hoạch như sau:
3.2. Robot mua hàng hoá
Có một robot đang ở nhà, chủ nhà cần mua một bếp ga, cà chua và nước
tương. Bộ lập kế hoạch phải lập ra kế hoạch để robot đến cửa hàng điện
máy mua bếp ga, đến siêu thị mua nước tương và cà chua sao cho nhanh
nhất về thời gian hay ít tốn kém nhất về tiền bạc và quay về nhà.
Nhấc B
ê
Đặt xuống NhấcC
ê
Đặt lên khối A
Nghiên cứu planning để giải bài toán xác định lộ trình
21
CHƯƠNG 2:
CÁC ĐỐI TƯỢNG TRONG LẬP KẾ
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.

thành công. Vấn đề đặt ra là sự thành công của agent được đánh giá như
thế nào và khi nào?
Để đánh giá như thế nào là một agent thành công các chuyên gia
đưa ra nguyên tắt độ đo thực thi. Độ đo này đánh giá mức độ hành động
của agent. Ví dụ, một robot dỡ hàng, độ đo hợp lí sẽ đo số hàng hoá dỡ
được trong một ca 8 giờ. Độ đo tinh vi hơn còn xét đến năng lượng tiêu
thụ (xăng, dầu,…) và tiếng ồn phát ra. Tuy nhiên, không có độ đo cố định
nào phù hợp với tất cả các agent.
Đánh giá khi nào là rất quan trọng. Qua đó có thể biết agent nào
làm việc nhanh, agent nào lười biếng.
Các chuyên gia luôn muốn tạo ra một agent sáng suốt. Agent này
biết trước kết quả của những hành động mà nó thực hiện, nhưng điều này
không khả thi trong thực tế. Vì các agent thường thực hiện hành động mà
không biết kết quả thế nào. Trừ khi nó thực hiện một “quẻ bói”. Tuy
nhiên, sẽ khả thi hơn để tạo ra một agent có ý thức, loại agent này thực
Nghiên cứu planning để giải bài toán xác định lộ trình
24
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