Đề tài Nghiên cứu planning để giải bài toán xác định lộ trình

thêm những bước nhằm thu được điều kiện tiên quyết chưa có. Các causal link được dùng để lưu vết điều này. 2.1. Mô tả bài toán Xét bài toán đi siêu thị: mục tiêu cần đạt được là mua được sữa, chuối, máy khoan và mang chúng về nhà. Hành động Go chỉ hành động đi từ nơi này đến nơi khác. Thứ hai, mô tả hành động Buy, mua một món hàng nào đó, bỏ qua vấn đề có tiền hay không. Trạng thái ban đầu gồm: ở nhà, máy khoan bán ở cửa hàng phần cứng, chuối và sữa được bán ở siêu thị. Tất cả được định nghĩa bởi toán tử sau, với HWS là cửa hàng phần cứng và SM là siêu thị: Op(ACTION:Start,EFFECT:At(Home) ∧ Sells(HWS,Drill) ∧ Sells(SM,Milk),Sells(SM,Banana)) Trạng thái mục tiêu gồm: có máy khoan, có sữa, có chuối, và ở nhả. Chúng được định nghĩa bởi bước Finish: Op(ACTION:Finish, PRECOND:Have(Drill) ∧ Have(Milk) ∧ Have(Banana) ∧ At(Home)) Các hành động được định nghĩa bởi các toán tử sau: Nghiên cứu planning để giải bài toán xác định lộ trình 91 Op(ACTION:Go(there),PRECOND:At(here), EFFECT:At(there) ∧ ¬At(here)) Op(ACTION:Buy(x),PRECOND:At(store) ∧ Sells(store,x), EFFECT:Have(x)) Bốn toán tử này được chứa trong cùng một nơi gọi là thư viện toán tử. Thư viện toán tử chứa tất cả các toán tử của bài toán. Kế hoạch ban đầu của bài toán được mô tả theo dạng lược đồ ở hình 5.1. 2.2. Áp dụng thuật toán POP cho bài toán Trong hình trên, có nhiều cách lựa chọn để giải quyết bài toán làm cho kế hoạch ban đầu trở nên phức tạp. Một số chọn lựa có thể thực hiện và một số thì không. Khi ta phát triển giải pháp của bài toán, ta sẽ thấy rõ những lựa chọn đúng và những lựa chọn không đúng. Để đơn giản, ta bắt đầu với những lựa chọn đúng. Trong hình 5.2 (hình trên), ta chọn ba hành động Buy để thu được ba điều kiện tiên quyết của hành động Finish. Vì thư viện toán tử chỉ chứa duy nhất một toán tử có thể thu được điều kiện tiên quyết của hành động Finish đó là Have(Drill), Have(Milk), Have(Banana), At(Home). Do đó ta chỉ có một lựa chọn là hành động Buy. Start Finish At(Home) Sells(SM,Banana) Sells(SM,Milk) Sells(HWS,Drill) Have(Drill) Have(Milk) Have(Banana) At(Home) Hình 5.1 Kế hoạch ban đầu cho bài toán shopping Nghiên cứu planning để giải bài toán xác định lộ trình 92 Đường in đậm trong hình là liên kết nhân quả. Ví dụ liên kết bên trái nhất trong hình có nghĩa là bước Buy(Drill) được thêm vào để thu được điều kiện tiên quyết Have(Drill) của bước Finish. Bộ lập kế hoạch sẽ chắc rằng điều kiện này được duy trì bằng cách bảo vệ nó: nếu một bước có thể xoá điều kiện Have(Drill) thì bước này không được chèn vào giữa bước Buy(Drill) và bước Finish. Các đường lợt trong hình thể hiện các ràng buộc thứ tự. Theo định nghĩa, tất cả các hành động đều bị ràng buộc sau hành động Start. Cũng vậy, tất cả các nguyên nhân đều được ràng buộc trước kết quả của chúng, vì vậy mỗi đường in đậm đều có một đường lợt dưới nó. Hình thứ hai trong hình 5.2 thể hiện ngữ cảnh sau khi bộ lập kế hoạch chọn lựa để thu được điều kiện tiên quyết Sells bằng cách liên kết chúng với trạng thái ban đầu. Ở đây, bộ lập kế hoạch cũng không có sự Start Finis Buy(Drill) Buy(Bananas)Buy(Milk) At(s), Sells(s,Drill) At(s), Sells(s,Milk) At(s), Sells(s,Bananas) Have(Drill), Havẹ(Milk), Have(Bananas), At(Home) Start Finish Buy(Drill) Buy(Bananas)Buy(Milk) At(HWS), Sells(HWS,Drill) At(SM), Sells(SM,Milk) At(SM), Sells(SM,Bananas) Have(Drill), Havẹ(Milk), Have(Bananas), At(Home) Hình 5.2 Hình trên: Kế hoạch cục bộ thu được ba trong số bốn điều kiện tiên quyết của Finish. Những đường in đậm thể hiện liên kết nhân quả. Hình dưới: Giới hạn kế hoạch cục bộ bằng cách thêm các liên kết để thu được các điều kiện tiên quyết Sells của các bước Buy. Nghiên cứu planning để giải bài toán xác định lộ trình 93 chọn lựa nào khác, vì thư viện toán tử cũng chỉ có một toán tử cho phép thu được điều kiện tiên quyết Sell của toán tử Buy. Cách tiếp cận của thuật toán POP giúp cải tiến hơn nhiều so với cách tiếp cận giải quyết bài toán. Trước tiên, ngoài tất cả những gì có thể mua, và tất cả những nơi có thể đến, chúng ta có thể chỉ chọn hành động Buy đúng và chỉ những nơi đúng, không lãng phí thời gian để xem xét những hành động và những nơi khác. Sau khi đã chọn hành động, ta không cần quan tâm đến việc sắp thứ tự chúng: bộ lập kế hoạch thứ tự cục bộ có thể thực hiện điều này sau. Hình 5.3 kế hoạch được mở rộng bằng cách chọn hai hành động Go để đi đến cửa hàng phần cứng và siêu thị, vậy, thu được điều kiện tiên quyết At của hành động Buy. Đến đây bộ lập kế hoạch có được nhiều thứ mà không cần phải thực hiện bất kì sự tìm kiếm nào. Sự tìm kiếm bắt đầu ở đây. Hai hành động Go có điều kiện tiên quyết chưa thu được, chúng tương tác qua lại lẫn nhau, vì agent không thể ở hai nơi cùng lúc. Mỗi hành động Go đều có điều kiện tiên quyết At(x), với x là nơi mà agent ở trước khi thực hiện hành động Start Finish Buy(Drill) Buy(Bananas)Buy(Milk) At(HWS), Sells(HWS,Drill) At(SM), Sells(SM,Milk) At(SM), Sells(SM,Bananas) Have(Drill), Havẹ(Milk), Have(Bananas), At(Home) Go(HWS) Go(SM) At(x) At(x) Hình 5.3 Kế hoạch cục bộ thu được điều kiện tiên quyết At của ba hành động Buy. Nghiên cứu planning để giải bài toán xác định lộ trình 94 Go. Giả sử bộ lập kế hoạch cố thu được điều kiện tiên quyết của Go(HWS) và Go(SM) bằng cách liên kết chúng với điều kiện At(Home) trong trạng thái ban đầu. Kết quả này trong kế hoạch thể hiện trong hình 5.4. Tuy nhiên, điều này làm nảy sinh vấn đề. Bước Go(HWS) tạo ra điều kiện At(HWS), nhưng xoá điều kiện At(Home). Vì vậy, nếu agent đi đến cửa hàng phần cứng, thì nó không thể đi từ nhà đến siêu thị được nữa. (Trừ khi, bộ lập kế hoạch đưa ra một bước khác đi từ cửa hàng phần cứng về nhà – nhưng ở đây chỉ có bước khởi đầu, không có bước nào khác thu được điều kiện At(Home).) Cũng vậy nếu agent đi đến siêu thị trước tiên thì nó không thể đi từ nhà đến cửa hàng phần cứng. Tới đây, ta đã tới ngõ cụt trong việc tìm kiếm giải pháp, nên phải quay trở lại và thử một lựa chọn khác. Điểm hay của thuật toán này là bộ lập kế hoạch không tốn nhiều thời gian để biết kế hoạch cục bộ này không thành công. Mấu chốt là các liên kết nhân quả trong kế hoạch cục bộ là các liên kết được bảo vệ. Một liên kết được bảo vệ bằng cách đảm bảo rằng các mâu thuẩn được đưa lên trước hoặc sau nó. Mâu thuẩn là những bước có thể xoá (hoặc gạt bỏ) những điều kiện được bảo vệ. Hình 5.5 thể hiện một mâu thuẩn và cách giải quyết nó. Start Finish Buy(Drill) Buy(Bananas)Buy(Milk) At(HWS), Sells(HWS,Drill) At(SM), Sells(SM,Milk) At(SM), Sells(SM,Bananas) Have(Drill), Havẹ(Milk), Have(Bananas), At(Home) Go(HWS) Go(SM) At(Home) At(Home) Hình 5.4. Kế hoạch có khuyết điểm là dẫn agent đến cửa hàng phần cứng và chợ Nghiên cứu planning để giải bài toán xác định lộ trình 95 causal link S1 →c S2 bị mâu thuẩn bởi bước mới S3 vì kết quả của S3 xoá c. Cách để giải quyết mâu thuẩn này là thêm những ràng buộc thứ tự để chắc rằng S3 không xen vào giữa S1 và S2. Nếu S3 được đặt trước S1 thì được gọi là demotion (hình 5.5b) và nếu nó được đặt sau S2, nó được gọi là promotion (hình 5.5c). Trong hình 5.4 không có cách nào để giải quyết mâu thuẩn mà mỗi bước Go đưa đến bước khác. Bất cứ bước Go nào thực hiện trước cũng xoá điều kiện At(Home) của bước còn lại. Khi bộ lập kế hoạch không thể giải quyết mâu thuẩn bằng cách nâng cấp hay giáng cấp, nó sẽ bỏ kế hoạch cục bộ và trở lại để thử một lựa chọn khác ở điểm trước nữa trong quá trình lập kế hoạch. Giả sử lựa chọn tiếp theo là thử một cách khác để thu được điều kiện tiên quyết là At(x) của bước Go(SM), lần này bằng cách thêm một causal link từ Go(HWS) đến Go(SM). Nói cách khác, kế hoạch là đi từ nhà đến cửa hàng phần cứng sau đó đi đến siêu thị. Điều này sinh ra một mâu thuẩn khác. Trừ khi kế hoạch được cải tiến hơn nữa, nếu không với kế hoạch này agent sẽ đi từ cửa hàng phần cứng đến siêu thị mà không mua máy khoan (điều này sẽ đặt ra câu hỏi tại sao nó đi đến cửa hàng Hình 5.5 Bảo vệ liên kết nhân quả. Hình (a), bước S3 huỷ điều kiện c được tạo nên bởi S1 và được bảo vệ bởi causal link từ S1 đến S2. Hình (b), S3 được nâng lên trước S1, và hình (c) nó được hạ xuống sau S2. S1 S3 S2 c ¬c (a) S2 S1 S3 c ¬c (b) S3 S2 S1 c ¬c (c) Nghiên cứu planning để giải bài toán xác định lộ trình 96 phần cứng trước tiên). Tuy điều này có thể giống với hành vi của con người, nhưng ta muốn agent lập kế hoạch tránh sự đãng trí này. Vì, bước Go(SM) sẽ xoá điều kiện tiên quyết At(HWS) của bước Buy(Drill), điều kiện này được được bảo vệ bởi causal link. Mâu thuẩn này được giải quyết bằng cách ràng buộc bước Go(SM) phải đến sau bước Buy(Drill). Hình 5.6 thể hiện kế hoạch cục bộ mới này. Chỉ điều kiện tiên quyết At(Home) của bước Finish vẫn chưa thu được. Thêm bước Go(Home) sẽ thu được nó, nhưng điều này đòi hỏi thu được điều kiện tiên quyết At(x). Các hướng giải quyết như sau: • Nếu chúng ta cố gắng thu được At(x) bằng cách liên kết với At(Home) ở trạng thái ban đầu, thì sẽ không có cách nào để giải quyết những mâu thuẩn tạo ra bởi Go(HWS) và Go(SM). • Nếu cố liên kết At(x) với bước Go(HWS), cũng không cách nào để giải quyết mâu thuẩn phát sinh bởi bước Go(SM), bước này bị ràng buộc phải đứng sau bước Go(HWS). Start Finish Buy(Drill) Buy(Bananas)Buy(Milk) At(HWS), Sells(HWS,Drill) At(SM), Sells(SM,Milk) At(SM), Sells(SM,Bananas) Have(Drill), Havẹ(Milk), Have(Bananas), At(Home) Go(HWS) Go(SM) At(Home) At(SWS) Go(Home) At(SM) Hình 5.6. Sự bảo vệ liên kết nhân quả trong kế hoạch đi siêu thị. Liên kết Go(HWS)  → )(HWSAt Buy(Drill) được bảo vệ bởi thứ tự bước Go(SM) sau bước Buy(Drill), và liên kết Go(SM)  → )( SMAt Buy(Milk/Bananas) được bảo vệ bởi thứ tự Go(Home) sau Buy(Milk) và Buy(Bananas). Nghiên cứu planning để giải bài toán xác định lộ trình 97 • Liên kết từ Go(SM) đến At(x) có nghĩa là x là SM, bây giờ bước Go(Home) sẽ xoá điều kiện At(SM). Điều này lại tạo ra mâu thuẩn với điều kiện tiên quyết At(SM) của Buy(Milk) và Buy(Bananas), nhưng mâu thuẩn này có thể giải quyết bằng cách sắp Go(Home) sau những hành động Buy. (Hình 5.6). Hình 5.7 thể hiện giải pháp hoàn chỉnh, với những bước được vẽ lại để cho thấy các ràng buộc thứ tự trên chúng. Kết qủa này hầu như là một kế hoạch trật tự tổng thể; chỉ có nhập nhằng giữa hai bước Buy(Milk) và Buy(Bananas) bước nào trước cũng được. Ta thấy rằng, với bài toán này, cách tiếp cận giải quyết bài toán cần rất nhiều trạng thái tìm kiếm, nhưng chỉ có vài trạng thái được sử dụng. Start Buy(Drill) At(HWS), Sells(HWS,Drill) Buy(Milk) At(SM), Sells(SM,Milk) Buy(Bananas) At(SM), Sells(SM,Bananas) Finish Havẹ(Milk), At(Home), Have(Bananas), Have(Drill) Go(HWS) At(Home) Go(SM) At(SWS) Go(Home) At(SM) Hình 5.7. Giải pháp của bài toán đi siêu thị. Nghiên cứu planning để giải bài toán xác định lộ trình 98 Thuật toán POP đã cải tiến vấn đề này rất nhiều. Theo nguyên tắc chuyển giao ít nhất, bộ lập kế hoạch chỉ cần tìm trong những không gian mà các kế hoạch con tương tác với nhau. Bên cạnh đó, các causal link cho phép bộ lập kế hoạch nhận ra khi nào cần bỏ đi một kế hoạch thất bại để không lãng phí thời gian mở rộng những phần không liên quan của kế hoạch. Nghiên cứu planning để giải bài toán xác định lộ trình 99 CHƯƠNG 6: MÔ HÌNH LẬP KẾ HOẠCH PHÂN Rà PHÂN CẤP 1. Phân rã phân cấp toán tử 2. Phân tích mô hình phân rã phân cấp Nghiên cứu planning để giải bài toán xác định lộ trình 100 CHƯƠNG 6: MÔ HÌNH LẬP KẾ HOẠCH PHÂN Rà PHÂN CẤP 1 PHÂN Rà PHÂN CẤP TOÁN TỬ 1.1. Đặt vấn đề Ví dụ về việc mua hàng ở siêu thị ở phần trước tạo ra các giải pháp với mức độ trừu tượng cao. Một kế hoạch như: [Go(Supermarket),Buy(Milk),Buy(Bananas),Go(Home)] là một mô tả cấp cao, nhưng với cách mô tả này để thu được kết quả trực tiếp phải có rất nhiều chỉ thị. Vì vậy, cách này không đủ khả năng để làm một bài toán lớn. Ví dụ, một kế hoạch chi tiết ở mức thấp như: [Forward(1cm),Turn(1 deg),Forward(1cm),…] thì cần đến hàng ngàn bước để giải quyết bài toán đi siêu thị. Chiều dài của không gian kế hoạch quá lớn mà những kĩ thuật đã nói ở phần trên có thể không tìm thấy giải pháp trong thời gian thích hợp. 1.2. Phân rã phân cấp là gì? Để giải quyết vấn đề này, hầu hết các bộ lập kế hoạch thực tế đều áp dụng ý tưởng phân rã phân cấp: một toán tử trừu tượng có thể được phân tích thành một nhóm các bước tạo thành một kế hoạch thực thi toán tử. Các kế hoạch phân rã này có thể được lưu trữ trong thư viện kế hoạch và được lấy ra khi cần. Nghiên cứu planning để giải bài toán xác định lộ trình 101 1.3. Ví dụ Xét bài toán xây khung nhà. Toán tử Xây(Nhà) có thể được phân tích thành một kế hoạch gồm bốn bước Xin được giấy phép, Thuê chủ thầu, Xây dựng và Trả tiền chủ thầu. Hình 6.1 mô tả các bước này. Các bước của kế hoạch này có thể phân rã thành những kế hoạch cụ thể hơn nữa. Hình 6.1 cũng thể hiện sự phân rã của bước Xây dựng. Sự phân rã sẽ tiếp tục cho đến khi ta tới bước cuối cùng là Đóng(Đinh). Kế hoạch hoàn chỉnh khi mỗi bước là một toán tử gốc – toán tử gốc là toán tử được thực thi trực tiếp bởi agent. Phân rã phân cấp hữu dụng nhất khi các toán tử có thể phân rã theo nhiều cách. Ví dụ, toán tử Xây tường có thể được phân rã thành một kế hoạch với các yêu cầu gỗ, gạch, bê tông hay nhựa. Xây nhà Thuê chủ thầu Xây dựng Xin được giấy phép Trả tiền chủ thầu Xây nền nhà Xây tường Lợp mái Xây các phòng Xây khung nhà phân rã thành phân rã thành Hình 6.1. Sự phân rã phân cấp của toán tử Xây nhà tạo thành kế hoạch thứ tự cục bộ Nghiên cứu planning để giải bài toán xác định lộ trình 102 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 Để thực hiện ý tưởng lập kế hoạch phân cấp, có hai vấn đề cần quan tâm: 1. Mở rộng của ngôn ngữ STRIPS chú ý đến những toán tử phát sinh. 2. Sửa đổi thuật toán lập kế hoạch cho phép thay thế những toán tử phát sinh bằng những toán tử phân rã của nó. 1.4.1. Mở rộng ngôn ngữ STRIPS Để hợp nhất phân rã phân cấp lại, ta phải thực hiện hai việc cho sự mô tả mỗi miền bài toán: 1) Chia tập các toán tử thành toán tử gốc và toán tử phát sinh. Trong ví dụ trên, Đóng(Đinh) là toán tử gốc và Xây(Nhà) là toán tử phát sinh. Sự phân biệt giữa toán tử gốc và toán tử phát sinh phụ thuộc vào agent thực thi kế hoạch. Đối với thầu khoán, toán tử Lắp ráp(Sàn nhà) là toán tử gốc, vì tất cả các thầu khoán đều ra lệnh cho công nhân lắp đặt. Đối với công nhân, Lắp ráp(Sàn nhà) là toán tử phát sinh, còn Đóng(Đinh) là toán tử gốc. 2) Thêm tập hợp các phương pháp phân rã. Mỗi phương pháp được mô tả theo dạng Decompose(o,p), nghĩa là toán tử phát sinh o có thể được phân tích thành kế hoạch p. Ví dụ, sự phân rã của Xây dựng từ hình 6.1: Decompose(Xây dựng, Plan(STEPS:{S1 : Xây dựng(nền),S2 : Xây dựng(Khung), S3 : Lợp(Mái),S4 : Xây dựng(Tường), S5 : Xây dựng(Các phòng)} ORDERINGS:{S1 p S2 p S3 p S5, S2 p S4 p S5}, Nghiên cứu planning để giải bài toán xác định lộ trình 103 BINDING:{}, LINKS:{S1  →Foundation S2,S2  →Frame S3,S2  →Frame S4, S3 →Roof S5,S4  →Walls S5})) Phương pháp phân rã giống như một tác vụ con hay một định nghĩa macro cho một toán tử. Bên cạnh đó, ta phải chắc rằng sự phân tích là sự thực thi chính xác của toán tử. Kế hoạch p thực thi chính xác toán tử o nếu nó nó thoả ba điều sau: 1. p phải nhất quán. (Không có sự mâu thuẩn nào trong thứ tự hay các ràng buộc các biến của p.) 2. Mỗi kết quả của o phải được xác nhận bởi ít nhất một bước của p (và không bị phủ nhận bởi bước nào khác sau bước p). 3. Mỗi điều kiện tiên quyết của các bước trong p phải được thu bởi một bước trong p hay là một trong những điều kiện tiên quyết của o. Điều này đảm bảo có thể thay thế một toán tử phát sinh bằng sự phân rã của nó, các hành động mắc vào nhau một cách hợp lý. Ta cần kiểm tra sự phát sinh mâu thuẩn từ sự tương tác giữa các bước mới với các điều kiện và những bước đang tồn tại cùng với các điều kiện, nhưng không cần phải lo về sự tương tác giữa các bước bên trong một bước phân rã. Tóm lại, việc lập kế hoạch phân cấp cho phép những kế hoạch rất phức tạp được xây dựng từ những kế hoạch con đơn giản hơn. Nó cũng cho phép phát sinh kế hoạch, lưu trữ và sau đó tái sử dụng lại trong các bài toán lập kế hoạch sau. 1.4.2. Thuật toán HD-POP Kế thừa bộ lập từ bộ lập kế hoạch POP để xây dựng bộ lập kế hoạch phân rã phân cấp, gọi là HD-POP. Thuật toán HD-POP như sau: Nghiên cứu planning để giải bài toán xác định lộ trình 104 So với POP, HD-POP có hai thay đổi quan trọng: 1) Cùng với việc tìm cách để thu được những điều kiện chưa đạt được trong kế hoạch, thuật toán phải tìm một cách để phân rã toán tử phát sinh vì cả hai phải được thực thi để tạo ra một kế hoạch hoàn chỉnh và cơ bản, không cần phải chỉ ra chọn lựa quay lui của kế hoạch hay kế hoạch khác. HD-POP là thuật toán đơn giản thực hiện từng tương tác một; các phương pháp tinh tế hơn có thể được dùng để làm giảm nhân tố rẽ nhánh. 2) Thuật toán lấy một kế hoạch như là đầu vào, không chỉ là mục tiêu. Thực chất, mục tiêu có thể được trình bày như kế hoạch Start- Finish, đây là cách tiếp cận của POP. Tuy nhiên, người sử dụng thường có nhu cầu tạo ra các chuỗi hành động như một kế hoạch, do đó cách tiếp cận này cho phép đầu vào là những kế hoạch mở rộng hơn. Để làm cho HD-POP làm việc, cần thay đổi SOLUTION? để kiểm tra mỗi bước của kế hoạch là bước gốc. Các hàm khác của POP không thay đổi. Có hai hàm mới: SELECT-NONPRIMTVE chọn một cách ngẫu nhiên một bước phát sinh từ kế hoạch. Hàm CHOOSE- DECOMPOSITION chọn phương pháp phân rã cho kế hoạch và áp dụng Thuật toán lập kế hoạch thứ tự cục bộ phân rã phân cấp, HD-POP. Trong mỗi lần lập của vòng lập trước tiên chúng ta thu được một điều kiện chưa đạt được (CHOOSE- OPERATOR), sau đó phân tích toán tử phát sinh (CHOOSE-DECOMPOSITION), sau đó giải quyết mâu thuẩn. function HD-POP(plan, operators, methods) returns plan inputs: plan, một kế hoạch trừu tượng với các bước bắt đầu và kết thúc (và những bước khác có thể có) loop do if SOLUTION?(plan) then return plan Sneed, c – SELECT-SUB-GOAL(plan) CHOOSE-OPERATOR(plan, operators, Sneed, c) Snonprim – SELECT-NONPRIMITIVE(plan) CHOOSE-DECOMPOSITION(plan, methods, Snonprim) RESOLVE-THREATS(plan) end Nghiên cứu planning để giải bài toán xác định lộ trình 105 nó. Nếu phương pháp được chọn để phân rã bước Snonprim, thì các trường của kế hoạch thay đổi như sau: • STEPS: Thêm tất cả các bước của phương pháp vào kế hoạch, nhưng xóa bước Snonprim. • BINDINGS: Thêm tất cả các ràng buộc các biến của phương pháp vào kế hoạch. Thuật toán thất bại nếu xảy ra tương phản. • ORDERINGS: Theo nguyên tắc chuyển giao ít nhất, ta thay thế mỗi ràng buộc thứ tự dạng Sa p Snonprim bởi ràng buộc thứ tự Sa đứng trước bước cuối cùng của phương pháp. Nghĩa là, nếu Sm là một bước của phương pháp, và không có bước Sj nào của phương pháp mà Sm p Sj, thì thêm ràng buộc Sa p Sm. Tương tự, thay thế mỗi ràng buộc dạng Snonprim p Sa bởi ràng buộc thứ tự Sa đứng sau bước đầu tiên của phương pháp. Sau đó chúng ta gọi RESOLVE- THREATS để thêm bất kì ràng buộc thứ tự nào cần thiết. • LINKS: Việc làm cho các causal link phù hợp với những bước con đúng của phương pháp dễ dàng hơn làm phù hợp với các ràng buộc thứ tự. Nếu Si →c Snonprim là một liên kết trong kế hoạch, thay thế nó bằng tập hợp các liên kết Si →c Sm, với mỗi Sm là một bước của phương pháp có c là điều kiện tiên quyết và không có bước nào trước nó có c là điều kiện tiên quyết. (Nếu có vài bước như vậy với c là điều kiện tiên quyết, thì đặt liên kết nhân quả cho mỗi bước. Nếu không có bước nào như vậy, thì liên kết từ Si có thể bị bỏ, bởi vì c là điều kiện tiên quyết không cần thiết của Snonprim.). Tương tự, mỗi liên kết Snonprim →c Sj trong kế hoạch, thay thế nó với một tập hợp các liên kết Sm →c Sj, với Sm là một bước của phương pháp có c là kết quả và không có bước nào sau nó có c là kết quả. Nghiên cứu planning để giải bài toán xác định lộ trình 106 Trong hình 6.2 chúng ta thể hiện lược đồ chi tiết của sự phân rã một bước kế hoạch, trong ngữ cảnh kế hoạch lớn hơn. Chú ý rằng một trong những liên kết nhân quả dẫn vào bước phát sinh Xây nhà kết thúc được gán cho bước đầu tiên của sự phân rã, nhưng causal link khác thì được gán cho bước sau. 2 PHÂN TÍCH MÔ HÌNH PHÂN Rà PHÂN CẤP Sự phân rã phân cấp giúp người lập trình có thể xem bài toán gồm thành phần với kích thước vừa phải. Các thành phần này có thể được liên kết lại theo sự phân cấp để tạo những kế hoạch lớn, mà không phải chịu chi phí khổng lồ của việc xây dựng các kế hoạch lớn từ các toán tử gốc. Phần sau đây sẽ nói rõ hơn về ý tưởng này. Trong ví dụ trên, giả sử có cách để kết hợp bốn toán tử trừu tượng lại với nhau để xây nhà. Sự kết hợp này được gọi là giải pháp trừu tượng - là kế hoạch chứa toán tử trừu tượng, nhưng phải là kế hoạch thống nhất và hoàn chỉnh. Việc tìm kiếm một giải pháp trừu tượng tương đối nhỏ nếu nó tồn tại không quá đắt. Tiếp tục quá trình này, ta có thể thu được kế hoạch gốc mà không phải quay lui quá nhiều. Mua đất Lấy tiền vay Xây nhà Dọn đến ở Sở hữu đất Có tiền Có(nhà) Mua đất Xin được giấy phép Thuê chủ thầu Lấy tiền vay Xây dựng Xin được giấy phép Dọn đến ở Sở hữu đất Có tiền Có(nhà) phân rã thành Hình 6.2. Sự phân rã chi tiết của một bước lập kế hoạch. Nghiên cứu planning để giải bài toán xác định lộ trình 107 2.1. Giải pháp thuận và giải pháp nghịch Giả sử việc tìm kiếm giải pháp trừu tượng và loại bỏ những kế hoạch trừu tượng khác (do những kế hoạch đó không nhất quán) là công việc hữu ích. Việc này có các thuộc tính sau đây: • Nếu p là một giải pháp trừu tượng, thì có một giải pháp gốc của p trừu tượng. Nếu có thuộc tính này, thì khi một giải pháp trừu tượng được tìm thấy, ta có thể bỏ tất cả các kế hoạch trừu tượng khác từ cây tìm kiếm. Thuộc tính này là thuộc tính giải pháp thuận. • Nếu một kế hoạch trừu tượng không nhất quán, thì không có giải pháp gốc nào của kế hoạch là trừu tượng. Nếu có thuộc tính này, ta bỏ đi tất cả các kế hoạch con của kế hoạch trừu tượng không nhất quán. Đây được gọi là thuộc tính giải pháp ngược vì nó cũng có nghĩa là tất cả các kế hoạch trừu tượng hoàn chỉnh của giải pháp gốc là các giải pháp trừu tượng. Hình 6.3 mô tả hai ý tưởng giải pháp thuận và giải pháp nghịch. Mỗi hộp trình bày một kế hoạch tổng thể (không chỉ một bước), và mỗi cung trình bày một bước phân tích mở rộng toán tử trừu tượng. Ở trên cùng kế hoạch rất trừu tượng, và ở dưới cùng là những kế hoạch chỉ với những bước gốc. Những hợp in đậm là những giải pháp (có thể trừu tượng), và những hộp chấm chấm là những kế hoạch không nhất quán. Các kế hoạch được đánh dấu với “X” không cần thử nghiệm bởi thuật toán lập kế hoạch. (Hình này chỉ thể hiện những kế hoạch chỉnh hay không nhất quán, bỏ qua những kế hoạch nhất quán nhưng không hoàn chỉnh.) Nghiên cứu planning để giải bài toán xác định lộ trình 108 Một mô hình không gian tìm kiếm đơn giản sẽ giúp ta hiểu rõ sự ảnh hưởng của các thuộc tính đến việc tìm kiếm. Giả sử rằng có ít nhất một giải pháp với n bước gốc, và thời gian để xử lí những mâu thuẩn giữa các bước và quản lí các ràng buộc là không đáng kể: điều đáng quan tâm đến thời gian lựa chọn tập các bước đúng. Hình 6.4 định nghĩa không gian tìm kiếm theo các tham số b, s và d. × × × × × × × × ××× × ×× × (a) Thuộc tính giải pháp th ậ (b) Thuộc tính giải pháp hị h Hình 6.3. Các thuộc tính solution thuận và nghịch trong không gian kế hoạch (các kế hoạch trừu tượng ở trên, các kế hoạch gốc ở dưới). Các hộp in đậm là các solution, đường chấm chấm là không thích hợp, và các hộp đánh dấu với X có thể được bỏ bớt trong việc tìm kiếm từ trái qua phải. Nghiên cứu planning để giải bài toán xác định lộ trình 109 Bộ lập kế hoạch không phân cấp sẽ phải tạo ra kế hoạch n bước, chọn trong số b khả năng cho mỗi kế hoạch. (Giả sử rằng số phân rã trên một bước phát sinh là b, thì giống như số toán tử mới có thể áp dụng cho điều kiện tiên quyết mở của bước gốc.). Vì vậy phải mất thời gian O(bn) trong trường hợp xấu nhất. Với bộ lập kế hoạch phân cấp, có thể chấp nhận phương pháp chỉ tìm kiếm những phân rã dẫn tới các giải pháp trừu tượng. (Với mô hình đơn giản này, chỉ 1 phân rã trong số b phân rã là tạo ra giải pháp. Trong các mô hình thực tế, cần quan tâm đến việc không có hoặc có nhiều hơn một giải pháp.) Bộ lập kế hoạch phải xem xét sb bước ở độ sâu d = 1. Ở độ sâu d = 2, phải xem xét sb bước khác đối mỗi bước b = 3 hệ số rẽ nhánh: số phương pháp phân rã trên một bước s = 4 các bước trong phương pháp phân rã • Dept h d = 0 d = 1 d = 2 d = 3 Hình 6.4. phần không gian tìm kiếm của phân rã phân cấp với độ sâu d = 3; nhân tố rẽ nhánh b = 3 phân rã trên một bước; s = 4 bước trên một phương pháp phân rã. Giải pháp sẽ có n = sd bước (trong trường hợp này n = 64). Chúng ta cũng giả sử rằng 1/b phân rã sẽ dẫn đến giải pháp. Nghiên cứu planning để giải bài toán xác định lộ trình 110 phân rã, hình này chỉ phân rã 1/b bước, với tổng số bước ở d = 2 là bs2. Vì vậy tổng số kế hoạch được xem xét là: )( 1 d d i i bsObs =∑ = Các thuộc tính giải pháp thuận và nghịch có những thuận lợi lớn. Không có những thuộc tính này, hay vài thuộc tính thay thế thích hợp, bộ lập kế hoạch phân cấp không tốt hơn bộ lập kế hoạch không phân cấp trong những trường hợp xấu nhất (mặc dù nó có thể tốt hơn trong những trường hợp thuận lợi). 2.2. Ví dụ Ví dụ sau đây không áp dụng thuộc tính giải pháp ngược, nên giải pháp trừu tượng không nhất quán. Tuy nhiên, vẫn có sự phân rã để giải quyết bài toán. Bài toán được lấy từ câu chuyện của O.Henry The Gift of the Magi. Đôi vợ chồng nghèo chỉ có hai vật có giá trị; anh ấy có một cái đồng hồ vàng và cô ấy có một mái tóc dài và đẹp. Họ có kế hoạch là muốn mua những món quà để đem lại niềm vui cho người kia. Anh ấy quyết định bán cái đồng hồ để mua cái lược thật đẹp cho vợ, và cô ấy cũng quyết định bán mái tóc để mua sợi dây đeo cho cái đồng hồ của chồng. Hình 6.5 mô tả bài toán. Nghiên cứu planning để giải bài toán xác định lộ trình 111 Hình 6.5b thể hiện kế hoạch kết quả trừu tượng không nhất quán. Tuy nhiên, vẫn có thể phân rã kế hoạch không nhất quán này thành giải pháp nhất quán nếu có sẵn các phương pháp phân rã đúng. Ở hình 6.5c bước “Cho Lược” được phân rã bằng phương pháp “kế hoạch từng phần”. Trong bước đầu tiên của sự phân rã, người chồng là chủ sở hữu của cây lược và đem nó cho vợ mình, trong khi đó đồng giao cái đồng hồ của mình để trả tiền lược vào ngày hôm sau. Ở bước thứ hai, đồng hồ được giao và trách nhiệm hoàn tất. Phương pháp tương tự phân rã bước “Cho Dây đeo”. Các bước “cho” được sắp thứ tự trước bước “giao”, cách phân rã này giải quyết bài toán. (a) Bài toán ban đầu Star Finish Đồng hồ Tóc Hạnhphúc(anhấy) Hạnhphúc(côấy) Star Finish Cho Lược Cho dây đeo (b) Kế hoạch trừu tượng không nhất á Đồnghồ Tóc ¬Đồnghồ Lược Hạnhphúc(côấy) Hạnhphúc(anhấy) Dây đeo ¬Tóc Star Finish Cho Lược (Mua chịu) Cho Dâyđeo (Mua chịu) Giao Đồng hồ Cắt Tóc Tóc Đồnghồ Lược Sởhửu(Đồng hồ) Hạnhphúc(côấy) Dâyđeo Sởhữu(Tóc) Hạnhphúc(anhấy) Đồnghồ Tóc ¬Đồnghồ ¬Sởhữu(Đồnghồ) ¬Tóc ¬Sởhữu(Tóc) (c) Sự phân rã của (b) thành một giải pháp nhất á Hình 6.5. (a) Bài toán The Gift of the Magi. (b) kế hoạch cục bộ không nhất quán, vì không có cách nào để sắp thứ tự hai bước trừu tượng mà không mâu thuẩn. (c) Sự phân rã giải quyết bài toán . Điều này vi phạm thuộc tính giải pháp ngược, bởi vì kế hoạch không nhất quán trong (b) bây giờ có một giải pháp. Đồnghồ Tóc Đồnghồ Tóc Nghiên cứu planning để giải bài toán xác định lộ trình 112 2.3. Sự phân rã và dùng chung Ở trên chúng ta đã trình bày phương pháp phân rã, một vấn đề được chia nhỏ thành những vấn đề con, giải quyết từng vấn đề con đó. Sau đó, kết hợp chúng lại với nhau tạo thành giải pháp. Cách tiếp cận này được gọi là chia để trị. Ví dụ: Công ty A muốn sản xuất và bán hàng. Bộ lập kế hoạch phân rã bài toán thành hai bài toán con gồm “xin giấy phép kinh doanh và sản xuất” và “xin giấy phép kinh doanh và bán hàng”. Khi kết hợp chúng lại, bộ lập kế hoạch gặp vấn đề khi thấy hai bước “xin giấy phép kinh doanh” khác nhau. Nếu điều kiện tiên quyết của “xin giấy phép kinh doanh” là “chưa có giấy phép kinh doanh” thì xin nghỉ không phải là cách để lựa chọn. Bài toán mô tả như sau: Để giải quyết vấn đề này, ta sử dụng cơ cấu dùng chung. Bài toán này sẽ dùng chung bước “xin giấy phép kinh doanh”. Bài toán áp dụng cơ cấu này như sau: Xin giấy phép kinh doanh Xin giấy phép kinh doanh Sản xuất Bán hàng Xin nghỉ Có giấy phép kinh doanh Không có giấy phép kinh doanh đang kinh doanh Có giấy phép kinh doanh Hình 6.6. Sự phân rã của bài toán sản xuất và bán hàng. Cách này không phù hợp Xin giấy phép kinh doanh Sản xuất Bán hàng Chưa có giấy phép kinh doanh Có giấy phép kinh doanh Có giấy phép kinh doanh Hình 6.7. Bài toán sản xuất và bán hàng sử dụng cơ cấu dùng chung với bước dùng chung là “xin giấy phép kinh doanh” Nghiên cứu planning để giải bài toán xác định lộ trình 113 Bên cạnh đó cũng có nhiều cách tiếp cận khác. Tuy nhiên cách tiếp cận này được sử dụng rộng rãi hơn. Nghiên cứu planning để giải bài toán xác định lộ trình 114 PHẦN 2: ỨNG DỤNG LẬP KẾ HOẠCH TRONG BÀI TOÁN TÌM ĐƯỜNG ĐI 1 Giới thiệu bài toán 2 Ý tưởng 3 Cài đặt agent 4 Các chiến lược 5 Kết quả thực nghiệm 6 So sánh lập trình kế hoạch và lập trình theo lý thuyết đồ thị Nghiên cứu planning để giải bài toán xác định lộ trình 115 PHẦN 2: ỨNG DỤNG LẬP KẾ HOẠCH TRONG BÀI TOÁN TÌM ĐƯỜNG ĐI 1 GIỚI THIỆU BÀI TOÁN Bài toán được đặt ra là xác định lộ trình cho một phương tiện giao thông có thể di chuyển qua nhiều trạm trong thành phố theo yêu cầu nhất định, ví dụ như đổ xăng, mua thực phẩm ở siêu thị, tránh kẹt xe nếu được thông báo trước …. và tất nhiên là phải đi đúng luật. Vấn đề ở đây là bài toán thể hiện mối quan hệ chặt chẽ giữa những trạng thái và những hành động cụ thể trong thế giới thực. Ví dụ như khi xác định đường đi giữa hai trạm, không nhất thiết chỉ có yêu cầu vể tối ưu hóa chiều dài đường đi. Người ta có thể yêu cầu tìm những con đường an toàn, tiết kiệm thời gian… Áp dụng lập trình kế hoạch cho một Agent được thiết kế đầy đủ, chúng ta có thể đáp ứng khá tốt được yêu cầu bài toán đặt ra. 2 Ý TƯỞNG Ý tưởng chính của để giải quyết bài toán là chúng ta sẽ đưa cho agent những chiến lược nhằm có thể nhanh chóng tìm ra những giải pháp tốt thoả mãn những yêu cầu. Thông qua những chiến lược agent có thể đưa ra những đánh giá cho các hành động sẽ thực hiện. Và vì không có chiến lược nào hoàn hảo cho mọi yêu cầu, nên để tìm ra giải pháp tốt, bộ lập kế họach có thể sử dụng kết hợp nhiều chiến lược cùng lúc. Nghiên cứu planning để giải bài toán xác định lộ trình 116 3 CÀI ĐẶT AGENT Agent : đơn giản chỉ bao gồm: 1) Trạng thái agent hiện tại: a. At(?) xác định vị trí của agent b. Pass (?) dã qua những con đường nào. Lưu vết agent nhằm hỗ trợ cho agent trong việc quyết định hành động 2) Các hành động Go(?) chỉ ra agent co thể đi đến đâu từ trạng thái hiện tại Plan : có dạng sau 4 CÁC CHIẾN LƯỢC Đây là những chiến lược giúp cho agent tìm đường có định hướng Chiến lược 1: ưu tiên chọn hành động nào mà khi thực hiện agent sẽ tiến gần đến đích nhất. Start Finish Pass(y) Pass(z) At(w ) Initial state At(x) Goal state Nghiên cứu planning để giải bài toán xác định lộ trình 117 Như hình trên chiến lược sẽ dể dàng chọn hành động đi đến vị trí 1, vì d1 là ngắn nhất, bất chấp việc có thể bị kẹt đường…. Đây là chiến lược đơn giản nhưng tỏ ra khá hiệu quả đối vời những đường đi thông thường. Chiến lược 2: khắc phục vài điểm yếu của chiến lược 1. Con đường được chọn sẽ được đánh giá trên tổng khoảng cách từ điểm định đến tới đích và chiều dài của con đường. Với ví dụ như hình trên, hành động đi đến vị trí 1vẫn được chọn vì d1 + d11 là nhỏ nhất, mặc dù vị trí 2 ở gần điểm kết thúc hơn (d21 ngắn nhất) nhưng do đoạn đường phải đi khi thực hiện hành động 2 quá dài (d2 + d21) (đây là khuyết điểm của chiến lược 1) nên hành động đi đến trạm 1 vẫn được đánh giá tốt hơn 1 23 EndStar d1 d2 d3 d11 d21 d31 1 2 3 End Star d1 d2 d3 Nghiên cứu planning để giải bài toán xác định lộ trình 118 Chiến lược 3: Ví dụ: Nếu sử dụng 2 chiến lược trên agent sẽ đi Start Æ 4 Æ 6 Æ5 Æ …… Chiến lược này lựa chọn hành động bằng cách đánh giá xem nếu đi đến điểm đó thì có thể đi đến những nào nữa, những điểm sắp tới có gần đích không, … Ở đây, giả sử đang ở đỉnh 4, agent sẽ quyết định dựa trên việc xem xét các đỉnh 2, 5, 6, 5. − Nếu đi tới 2 thì có thể đến End. − Nếu tới 6, vì từ 6 đến End là ngược chiều không đi được, phải đến 7 hay 5. − Nếu tới 5, phải vòng trở lại để qua các đỉnh còn lại. − Nếu tới 7 thì phải vòng lại như tới 6. Cuối cùng, ta chọn đỉnh 2. 1 2 End Star 4 5 6 7 Nghiên cứu planning để giải bài toán xác định lộ trình 119 5 KẾT QUẢ THỰC NGHIỆM Đi từ chợ Chùa Xá Lợi (Bà Huyện Thanh Quan) đến Bệnh Viện Từ Dũ (Nguyễn Thị Minh Khai) Nhập: Điểm 1 chỉ vị trí chùa Xá Lợi trên đường Bà Huyện Thanh Quan. Điểm 2 chỉ vị trí bệnh viện Từ Dũ trên đường Nguyễn Thị Minh Khai. 5.1. Chiến lược 1 và bộ lập kế hoạch truy hồi Xuất: Nghiên cứu planning để giải bài toán xác định lộ trình 120 Chọn liên kết Start ---> End Vị trí hiện tại có thể được đi đến từ 2 đường Đường 1 : Nguyễn Thị Minh Khai Được đánh giá = 177 Đường 2 : Nguyễn Thị Minh Khai Được đánh giá = 211 Chọn đường : Nguyễn Thị Minh Khai vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Nguyễn Thị Minh Khai Được đánh giá = 157 Đường 2 : Lương Hữu Khánh Được đánh giá = 184 Đường 3 : Nguyễn Thị Minh Khai Được đánh giá = 203 Nghiên cứu planning để giải bài toán xác định lộ trình 121 Loại bỏ đường : Nguyễn Thị Minh Khai vì đã di qua trong liên kết Chọn đường : Nguyễn Thị Minh Khai vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Nguyễn Thị Minh Khai Được đánh giá = 138 Đường 2 : Nguyễn Thượng Hiền Được đánh giá = 143 Đường 3 : Nguyễn Thị Minh Khai Được đánh giá = 177 Loại bỏ đường : Nguyễn Thị Minh Khai vì đã di qua trong liên kết Chọn đường : Nguyễn Thị Minh Khai vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Nguyễn Thị Minh Khai Được đánh giá = 119 Đường 2 : Tôn Thất Tùng Được đánh giá = 151 Đường 3 : Nguyễn Thị Minh Khai Được đánh giá = 157 Loại bỏ đường : Nguyễn Thị Minh Khai vì đã di qua trong liên kết Nghiên cứu planning để giải bài toán xác định lộ trình 122 Chọn đường : Nguyễn Thị Minh Khai vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 4 đường Đường 1 : Cách Mạng Tháng Tám Được đánh giá = 90 Đường 2 : Nguyễn Thị Minh Khai Được đánh giá = 115 Đường 3 : Cách Mạng Tháng Tám Được đánh giá = 134 Đường 4 : Nguyễn Thị Minh Khai Được đánh giá = 138 Loại bỏ đường : Nguyễn Thị Minh Khai vì đã di qua trong liên kết Chọn đường : Cách Mạng Tháng Tám vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 4 đường Đường 1 : Cách Mạng Tháng Tám Được đánh giá = 75 Đường 2 : Võ Văn Tần Được đánh giá = 82 Đường 3 : Cách Mạng Tháng Tám Được đánh giá = 119 Đường 4 : Võ Văn Tần Được đánh giá = 132 Nghiên cứu planning để giải bài toán xác định lộ trình 123 Loại bỏ đường : Cách Mạng Tháng Tám vì đã di qua trong liên kết Chọn đường : Cách Mạng Tháng Tám vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Nguyễn Thị Diệu Được đánh giá = 62 Đường 2 : Cách Mạng Tháng Tám Được đánh giá = 65 Đường 3 : Cách Mạng Tháng Tám Được đánh giá = 90 Loại bỏ đường : Cách Mạng Tháng Tám vì đã di qua trong liên kết Chọn đường : Nguyễn Thị Diệu vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Bà Huyện Thanh Quan Được đánh giá = 47 Đường 2 : Nguyễn Thị Diệu Được đánh giá = 75 Đường 3 : Nguyễn Thị Diệu Được đánh giá = 77 Loại bỏ đường : Nguyễn Thị Diệu vì đã di qua trong liên kết Nghiên cứu planning để giải bài toán xác định lộ trình 124 Chọn đường : Bà Huyện Thanh Quan vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 2 đường Đường 1 : Bà Huyện Thanh Quan Được đánh giá = 32 Đường 2 : Nguyễn Đình Chiểu Được đánh giá = 63 Chọn đường : Bà Huyện Thanh Quan vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Bà Huyện Thanh Quan Được đánh giá = 15 Đường 2 : Hồ Xuân Hương Được đánh giá = 40 Đường 3 : Hồ Xuân Hương Được đánh giá = 52 Chọn đường : Bà Huyện Thanh Quan vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Bà Huyện Thanh Quan Được đánh giá = 0 Đường 2 : Ngô Thời Nhiệm Được đánh giá = 32 Đường 3 : Ngô Thời Nhiệm Nghiên cứu planning để giải bài toán xác định lộ trình 125 Được đánh giá = 43 Chọn đường : Bà Huyện Thanh Quan vì có độ đánh giá nhỏ nhất Thành công và kết thúc 5.2. Chiến lược 2 và bộ lập kế hoạch truy hồi Xuất: Chọn liên kết Start ---> End Vị trí hiện tại có thể được đi đến từ 2 đường Đường 1 : Nguyễn Thị Minh Khai Được đánh giá = 208 Đường 2 : Nguyễn Thị Minh Khai Được đánh giá = 221 Chọn đường : Nguyễn Thị Minh Khai vì có độ đánh giá nhỏ nhất Nghiên cứu planning để giải bài toán xác định lộ trình 126 Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Nguyễn Thị Minh Khai Được đánh giá = 185 Đường 2 : Lương Hữu Khánh Được đánh giá = 204 Đường 3 : Nguyễn Thị Minh Khai Được đánh giá = 234 Loại bỏ đường : Nguyễn Thị Minh Khai vì đã di qua trong liên kết Chọn đường : Nguyễn Thị Minh Khai vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Nguyễn Thượng Hiền Được đánh giá = 160 Đường 2 : Nguyễn Thị Minh Khai Được đánh giá = 169 Đường 3 : Nguyễn Thị Minh Khai Được đánh giá = 205 Loại bỏ đường : Nguyễn Thị Minh Khai vì đã di qua trong liên kết Chọn đường : Nguyễn Thượng Hiền vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Nguyễn Thượng Hiền Nghiên cứu planning để giải bài toán xác định lộ trình 127 Được đánh giá = 146 Đường 2 : Nguyễn Thượng Hiền Được đánh giá = 174 Đường 3 : Nguyễn Sơn Hà Được đánh giá = 274 Loại bỏ đường : Nguyễn Thượng Hiền vì đã di qua trong liên kết Chọn đường : Nguyễn Thượng Hiền vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 4 đường Đường 1 : Nguyễn Thượng Hiền Được đánh giá = 143 Đường 2 : Võ Văn Tần Được đánh giá = 153 Đường 3 : Nguyễn Thượng Hiền Được đánh giá = 157 Đường 4 : Võ Văn Tần Được đánh giá = 274 Loại bỏ đường : Nguyễn Thượng Hiền vì đã di qua trong liên kết Chọn đường : Nguyễn Thượng Hiền vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Nguyễn Đình Chiểu Nghiên cứu planning để giải bài toán xác định lộ trình 128 Được đánh giá = 111 Đường 2 : Nguyễn Thượng Hiền Được đánh giá = 147 Đường 3 : Nguyễn Thượng Hiền Được đánh giá = 170 Loại bỏ đường : Nguyễn Thượng Hiền vì đã di qua trong liên kết Chọn đường : Nguyễn Đình Chiểu vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Cách Mạng Tháng Tám Được đánh giá = 73 Đường 2 : Cách Mạng Tháng Tám Được đánh giá = 94 Đường 3 : Nguyễn Đình Chiểu Được đánh giá = 98 Chọn đường : Cách Mạng Tháng Tám vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Hồ Xuân Hương Được đánh giá = 66 Đường 2 : Cách Mạng Tháng Tám Được đánh giá = 74 Đường 3 : Cách Mạng Tháng Tám Nghiên cứu planning để giải bài toán xác định lộ trình 129 Được đánh giá = 78 Loại bỏ đường : Cách Mạng Tháng Tám vì đã di qua trong liên kết Chọn đường : Hồ Xuân Hương vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Nguyễn Thông Được đánh giá = 50 Đường 2 : Hồ Xuân Hương Được đánh giá = 58 Đường 3 : Hồ Xuân Hương Được đánh giá = 86 Loại bỏ đường : Hồ Xuân Hương vì đã di qua trong liên kết Chọn đường : Nguyễn Thông vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 4 đường Đường 1 : Ngô Thời Nhiệm Được đánh giá = 46 Đường 2 : Nguyễn Thông Được đánh giá = 58 Đường 3 : Nguyễn Thông Được đánh giá = 64 Đường 4 : Ngô Thời Nhiệm Nghiên cứu planning để giải bài toán xác định lộ trình 130 Được đánh giá = 79 Loại bỏ đường : Nguyễn Thông vì đã di qua trong liên kết Chọn đường : Ngô Thời Nhiệm vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Bà Huyện Thanh Quan Được đánh giá = 15 Đường 2 : Ngô Thời Nhiệm Được đánh giá = 63 Đường 3 : Ngô Thời Nhiệm Được đánh giá = 80 Loại bỏ đường : Ngô Thời Nhiệm vì đã di qua trong liên kết Chọn đường : Bà Huyện Thanh Quan vì có độ đánh giá nhỏ nhất Thành công và kết thúc Nghiên cứu planning để giải bài toán xác định lộ trình 131 5.3. Chiến lược 3 và bộ lập kế hoạch truy hồi Xuất: Chọn liên kết Start ---> End Vị trí hiện tại có thể được đi đến từ 2 đường Đường 1 : Nguyễn Thị Minh Khai Được đánh giá = 157 Đường 2 : Nguyễn Thị Minh Khai Được đánh giá = 201 Chọn đường : Nguyễn Thị Minh Khai vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Nguyễn Thị Minh Khai Được đánh giá = 138 Đường 2 : Lương Hữu Khánh Nghiên cứu planning để giải bài toán xác định lộ trình 132 Được đánh giá = 151 Đường 3 : Nguyễn Thị Minh Khai Được đánh giá = 177 Loại bỏ đường : Nguyễn Thị Minh Khai vì đã di qua trong liên kết Chọn đường : Nguyễn Thị Minh Khai vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Nguyễn Thị Minh Khai Được đánh giá = 119 Đường 2 : Nguyễn Thượng Hiền Được đánh giá = 132 Đường 3 : Nguyễn Thị Minh Khai Được đánh giá = 157 Loại bỏ đường : Nguyễn Thị Minh Khai vì đã di qua trong liên kết Chọn đường : Nguyễn Thị Minh Khai vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Nguyễn Thị Minh Khai Được đánh giá = 90 Đường 2 : Tôn Thất Tùng Được đánh giá = 134 Đường 3 : Nguyễn Thị Minh Khai Nghiên cứu planning để giải bài toán xác định lộ trình 133 Được đánh giá = 138 Loại bỏ đường : Nguyễn Thị Minh Khai vì đã di qua trong liên kết Chọn đường : Nguyễn Thị Minh Khai vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 4 đường Đường 1 : Cách Mạng Tháng Tám Được đánh giá = 75 Đường 2 : Nguyễn Thị Minh Khai Được đánh giá = 82 Đường 3 : Cách Mạng Tháng Tám Được đánh giá = 119 Đường 4 : Nguyễn Thị Minh Khai Được đánh giá = 119 Loại bỏ đường : Nguyễn Thị Minh Khai vì đã di qua trong liên kết Chọn đường : Cách Mạng Tháng Tám vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 4 đường Đường 1 : Cách Mạng Tháng Tám Được đánh giá = 62 Đường 2 : Võ Văn Tần Được đánh giá = 62 Đường 3 : Cách Mạng Tháng Tám Nghiên cứu planning để giải bài toán xác định lộ trình 134 Được đánh giá = 90 Đường 4 : Võ Văn Tần Được đánh giá = 90 Loại bỏ đường : Cách Mạng Tháng Tám vì đã di qua trong liên kết Chọn đường : Cách Mạng Tháng Tám vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Cách Mạng Tháng Tám Được đánh giá = 47 Đường 2 : Nguyễn Thị Diệu Được đánh giá = 47 Đường 3 : Cách Mạng Tháng Tám Được đánh giá = 75 Loại bỏ đường : Cách Mạng Tháng Tám vì đã di qua trong liên kết Chọn đường : Cách Mạng Tháng Tám vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Nguyễn Đình Chiểu Được đánh giá = 32 Đường 2 : Cách Mạng Tháng Tám Được đánh giá = 40 Đường 3 : Cách Mạng Tháng Tám Nghiên cứu planning để giải bài toán xác định lộ trình 135 Được đánh giá = 62 Loại bỏ đường : Cách Mạng Tháng Tám vì đã di qua trong liên kết Chọn đường : Nguyễn Đình Chiểu vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 2 đường Đường 1 : Bà Huyện Thanh Quan Được đánh giá = 15 Đường 2 : Nguyễn Đình Chiểu Được đánh giá = 77 Chọn đường : Bà Huyện Thanh Quan vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Bà Huyện Thanh Quan Được đánh giá = 0 Đường 2 : Hồ Xuân Hương Được đánh giá = 32 Đường 3 : Hồ Xuân Hương Được đánh giá = 32 Chọn đường : Bà Huyện Thanh Quan vì có độ đánh giá nhỏ nhất Vị trí hiện tại có thể được đi đến từ 3 đường Đường 1 : Bà Huyện Thanh Quan Được đánh giá = 0 Nghiên cứu planning để giải bài toán xác định lộ trình 136 Đường 2 : Ngô Thời Nhiệm Được đánh giá = 15 Đường 3 : Ngô Thời Nhiệm Được đánh giá = 15 Chọn đường : Bà Huyện Thanh Quan vì có độ đánh giá nhỏ nhất Thành công và kết thúc 6 SO SÁNH LẬP TRÌNH KẾ HOẠCH VÀ LẬP TRÌNH THEO LÝ THUYẾT ĐỒ THỊ 6.1. Thuật toán DijkstraMoore Đây là một thuật toán rất mạnh trong việc xác định con đường ngắn nhất theo khoảng cách. Thuật giải chi tiết 1 Đặt L = {v0}, δ(v0) = 0. Với v ∈ V – {v0} Đặt δ(v) = c(v0, v) và π(v) = v0 2 Nếu mọi đỉnh của G đều thuộc L thì dừng. 3 Nếu không, chọn v ∉ L sao cho δ(v) nhỏ nhất. Đặt v* = v. Đưa thêm đỉnh v* và cạnh π(v*)v* vào L 4 Với mọi w ∈ V\L, nếu δ(w) > δ(v*) + c(v*,w) thì đặt δ(w) = δ(v*) + c(v*,w) và π(w) = v* Trở về bước 2. 6.2. Đối với lập trình kế hoạch Lập trình kế hoạch thường sử dụng tốt trong những bài toán thực tế. Nghiên cứu planning để giải bài toán xác định lộ trình 137 Thuật toán chi tiết đã được trình bày ở trên. ™ Các ưu khuyết điểm của hai cách tiếp cận này như sau: Thuật toán DijkstraMoore Lập trình kế hoạch Ưu điểm − Thuật toán ứng dụng rất tốt đối với các bài toán chỉ đơn thuần trên lý thuyết. − Luôn tìm ra con đường tối ưu ứng với một bộ trọng số được đưa vào. − Cập nhật dễ dàng những thay đổi của môi trường, từ đó có những hành động cụ thể. − Sử dụng trên môi trường động. − Không tìm kiếm như các thuật toán lí thuyết đồ thị, lập trình kế hoạch định hướng lựa chọn hành động theo những chiến lược đã đưa ra. Khuyết điểm − Đối với những bài toán trong thế giới thực việc xác định trọng số còn phụ thuộc vào nhiều yếu tố khác như: thời gian, độ an toàn, nhiên liệu,…Thuật toán này không thể xác định được những trọng số này. − Trọng số trong bài toán thế − Giải pháp lập trình kế hoạch đưa ra không phải lúc nào cũng là giải pháp tối ưu. Giải pháp này có thể đáp ứng nhiều nhu cầu thực tế của con người nhưng chưa chắc đó là giải pháp tốt nhất. − Khi áp dụng lập trình kế Nghiên cứu planning để giải bài toán xác định lộ trình 138 giới thực có thể thay đổi khi môi trường thay đổi, thuật toán DijkstraMoore không thể cập nhật được sự thay đổi này. − Sử dụng hoàn toàn trên môi trường tĩnh. − Thuật toán tìm kiếm gần như toàn bộ đồ thị nên chi phí và thời gian tìm kiếm khá lớn hoạch để giải một bài toán thuần về lý thuyết, cũng không hẵn đưa ra giải pháp tối ưu. Nghiên cứu planning để giải bài toán xác định lộ trình 139 PHẦN 3: TỔNG KẾT Luận văn hổ trợ tìm đường đi trong thành phố Hồ Chí Minh đáp ứng những vấn đề quan trọng thường thấy trong thực tế như luật đi đường, các vị trí mấu chốt quan trọng được đặt trong thành phố, xuất hiện sự cố đột xuất làm tắt nghẽn đường, v.v...Những hổ trợ này giúp những người chưa thông thạo các con đường trong thành phố có thể đi lại dễ dàng đáp ứng về nhiều mặt như tiết kiệm thời gian, độ an toàn, v.v.. mà vẫn đảm bảo đi đến các nơi cần thiết. 1 NHỮNG GÌ Đà LÀM ĐƯỢC − Luận văn đã xây dựng một số quận trong thành phố Hồ Chí Minh: quận 3, quận 5, một phần quận 10 và một phần quận 1. − Cài đặt với các luật: đường một chiều, cấm quẹo trái. − Cài đặt thuật toán POP truy hồi và POP tiến − Cài đặt 3 chiến lược định hướng cho agent − Cài đặt thuật toán Diskramore của lý thuyết đồ thị để so sánh với thuật toán lập kế hoạch − Xây dựng chương trình để cập nhật bản đồ thành phố. 2 NHỮNG GÌ CHƯA LÀM ĐƯỢC Do có nhiều giới hạn về thời gian, tài liệu và những vấn đề khác. Luận văn chưa hoàn chỉnh cần cải tiến nhiều, mong quý thầy cô thông cảm. Nghiên cứu planning để giải bài toán xác định lộ trình 140 3 HƯỚNG PHÁT TRIỂN Luận văn có thể phát triển rất nhiều trong tương lai: Xây dựng toàn bộ bản đồ thành phố Thêm tất cả các luật giao thông trên các con đường, đối với mọi loại phương tiện Thêm các vị trí quan trọng như trụ sở nhà nước, trường học, bệnh viện, ... Nghiên cứu planning để giải bài toán xác định lộ trình 141 TÀI LIỆU THAM KHẢO Stuart J. Russell and Peter Norvig, Artificial Intelligence A Modern Approach, Alan, Dr. Jussi Rintanen, Principles of Planning in Artificial Intelligence, Exam: compulsory for ACS students, bulding 101, room SR-01-018, October 14. Malte Helmert, An Introduction to PDDL (Planning Domain Difinition Language), Exam: compulsory for ACS students, bulding 101, room SR- 01-018, October 16. Stephen J. J. Smith, Dana Nau, Tom Throop, (1998), Computer Bridge: A Big Win for AI Planning, AI Magazine, 19(2): 93-105. Currie, K. and Tate, (1974), O-Plan – control in the open planner architecture. BCS Expert Systems Conference, Cambridge University Press, UK, A. 1985. Sacerdoti, Planning in a hierarchy of abstraction spaces, Artificial Intelligence 5: 115-135, E. D. Sacerdoti, (1977), A Structure for Plans and Behavisor, American Elsevier Publishing Company, NewYork, E. D. Austin Tate, and - Representing Plans and other Synthesised Artifacts as a Set of Constraints, Artificial Intelligence Applications Institute, Division of Informatics, The University of Edinburgh. Austin Tate, Coordinating the activities of a Planner and an Execution Agent, Artificial Intelligence Applications Institute, Division of Informatics, The University of Edinburgh. Nghiên cứu planning để giải bài toán xác định lộ trình 142 Ait-Kaci, H. and Nasr. R, (1986), LOGIN: a logic programming language with built-in inheritance, Journal of Logic Programming, 3(3): 185-215. Allen. J. F., Hendler. J. and Tate. A., (1990), editors, Readings in Planning, Morgan Kaufmann, San Mateo, California.