Bài giảng Trí tuệ nhân tạo - Chương 11: Lập kế hoạch

Trí Tuệ Nhân Tạo

Nguyễn Nhật Quang

[email protected]

Viện Công nghệ Thông tin và Truyền thông

Trường Đại học Bách Khoa Hà Nội

Năm học 2009-2010

Nội dung môn học:

Giới thiệu về Trí tuệ nhân tạo

Tác tử

Giải quyết vấn đề: Tìm kiếm, Thỏa mãn ràng buộc

Logic và suy diễn

Biểu diễn tri thức

Suy diễn với tri thức không chắc chắn

Học máy

Lập kế hoạch

Trí Tuệ Nhân Tạo

2

Lập kế hoạch của con người (1)

Hành động mà không có kế hoạch (rõ ràng)

Đối với các mục tiêu gần (tức thì)

Ví dụ: Bật máy tính lên

Đối với các hành động (hoạt động) đã được huấn luyện (tập

luyện) kỹ

Ví dụ: Lái xe ô-tô

Khi một quá trình hành động có thể được thay đổi thoải mái

Ví dụ: Đi mua sắm ở siêu thị

Trí Tuệ Nhân Tạo

3

Lập kế hoạch của con người (2)

Hành động theo kế hoạch

Khi gi

ả

i quy

ế

t m

ộ

t tình hu

ố

ng m

ớ

i – Vd: Chuy

ể

n nhà (

đế

n m

ộ

t n

ơ

i

ở mới)

Đối với các nhiệm vụ (công việc) phức tạp – Vd: Xây dựng kế

ho

ạ

ch h

ọ

c t

ậ

p cho m

ộ

t h

ọ

c k

ỳ

Khi môi trường hoạt động có chứa nguy cơ rủi ro/chi phí cao –

Vd: Quản lý nhà máy năng lượng hạt nhân

Khi cần hoạt động cộng tác với những người khác – Vd: Xây

dựng một ngôi nhà

Con ng

ườ

i th

ườ

ng ch

ỉ

l

ậ

p k

ế

ho

ạ

ch khi th

ự

c s

ự

c

ầ

n thi

ế

t

Bởi vì việc lập kế hoạch là phức tạp và tốn thời gian (chi phí vs.

lợi ích)

Con người thường chỉ cần các kế hoạch tốt hơn là tối ưu

Trí Tuệ Nhân Tạo

4

Lập kế hoạch của máy tính

Lập kế hoạch (Planning) của máy tính

Là quá trình tính toán c

ủ

a máy tính

để

l

ự

a ch

ọ

n và t

ổ

ch

ứ

c các

hành động, dựa trên dự đoán (trước) các kết quả của các hành

động đó

Nh

ằ

m m

ụ

c

đ

ích

đạ

t

đượ

c m

ộ

t s

ố

m

ụ

c tiêu (objectives) xác

đị

nh

Lập kế hoạch tối ưu: Đạt được các mục tiêu một cách tối ưu nhất

Các kiểu bài toán l

ậ

p kế ho

ạ

ch

Với các ràng buộc về thời gian (Time constraints)

Với các ràng buộc về thời gian và tài nguyên (Time and resource

constraints) – Bài toán l

ậ

p l

ị

ch (Scheduling)

Với các ràng buộc về thời gian và tài nguyên, các điều kiện áp

dụng (applicability conditions) của các hành động, và các tác

độ

ng (effects) c

ủ

a các hành

độ

ng

đố

i v

ớ

i tr

ạ

ng thái c

ủ

a bài toán

Trí Tuệ Nhân Tạo

5

Mô hình khái niệm

Mô hình khái niệm (Conceptual model) cho bài toán lập

k

ế

ho

ạ

ch

đượ

c bi

ể

u di

ễ

n b

ằ

ng m

ộ

t h

ệ

chuy

ể

n tr

ạ

ng thái

Một hệ chuyển trạng thái (State-transition system)

đượ

c bi

ể

u di

ễ

n b

ở

i 4 thành ph

ầ

n:

Σ

= (

S

,

A

,

E

,

γ

)

S={s₁,s₂,…}: Tập hữu hạn các trạng thái (states) có thể của bài

toán

A={a₁,a₂,…}: Tập hữu hạn các hành động (actions) có thể được

thực hiện

E={e₁,e₂,…}:

T

ậ

p h

ữ

u h

ạ

n

các s

ự

ki

ệ

n (events)

có th

ể

x

ả

y ra trong

quá trình thực hiện kế hoạch

γ: S×A×E→S: Hàm chuyển trạng thái (a state-transition function)

Trí Tuệ Nhân Tạo

6

Biểu diễn bằng đồ thị

Một hệ chuyển trạng thái Σ = (S, A, E,γ) có thể được biểu

di

ễ

n b

ằ

ng m

ộ

t

đồ

th

ị

có nhãn và có h

ướ

ng (a directed

labelled graph) G = (N_G, E_G), trong đó:

Mỗi nút biểu diễn một trạng thái trong tập S

Tức là: N_G≡S

Mỗi cạnh liên kết từ s đến s′ (s, s′∈N_G) có nhãn là (a,e) với a∈A,

e

∈

E

Tức là: Một cạnh (s,(a,e),s’)∈E_G, nếu và chỉ nếu s′∈γ(s,a,e)

Trí Tuệ Nhân Tạo

7

Biểu diễn bằng đồ thị – Ví dụ

Các trạng thái S: s₀…s₅(phụ thuộc vào các đối tượng: rô-bốt, cần trục, thùng hàng, …)

Các hành động A: cần trục nhấc (đặt) thùng hàng khỏi (lên) tấm nâng, rô-bốt di

chuyển giữa 2 vị trí, cần trục nhấc (đặt) thùng hàng khỏi (lên) rô-bốt

Không có sự kiện E = ∅

crane

move1

s₀

s₂

s₅

cont.

pallet

robot

pallet

cont.

robot

move2

move1

location1

take

location2

location1

location2

put

location1

move1

location2

put

take

move2

crane

cont.

crane

cont.

crane

s₁

s₃

s₄

load

pallet

robot

pcaolnlte.t

robot

move2

unload

location1

location2

location1

location2

location1

location2

(http://www.inf.ed.ac.uk/teaching/courses/plan/)

Trí Tuệ Nhân Tạo

8

Hệ chuyển trạng thái

Chuyển trạng thái: γ(s,a,e)

S

ự

ki

ệ

n trung tính (neutral event)

,

đượ

c ký hi

ệ

u là ε

,

đượ

c

dùng để biểu diễn đối với các chuyển trạng thái gây nên bởi

chỉ các hành động

Chuy

ể

n tr

ạ

ng thái

γ

(

s

,

a

,

ε

)

, v

ớ

i

s

∈

S

,

a

∈

A

:

đượ

c ký hi

ệ

u (ng

ắ

n g

ọ

n)

bằng γ(s,a)

Hành động trung tính (neutral action), được ký hiệu là no-

op, được dùng để biểu diễn đối với các chuyển trạng thái gây

nên bởi chỉ các sự kiện

Chuyển trạng thái γ(s,no-op,e) , với s∈S, e∈E : được ký hiệu

(ngắn gọn) bằng γ(s,e)

Trong biểu diễn bằng đồ thị

Nhãn (a,ε) được ký hiệu ngắn gọn bằng a

Nhãn (no-op,e) được ký hiệu ngắn gọn bằng e

Trí Tuệ Nhân Tạo

9

Các hành động vs. Các sự kiện

Cả hành động (action) và sự kiện (event) đều ảnh hưởng đến

sự tiến triển của một hệ chuyển trạng thái

Các hành động: Thể hiện các chuyển trạng thái được điều

khiển bởi bộ thực hiện kế hoạch (plan executor)

Nếu hành động a∈A và γ(s, a, ε) ≠ ∅, thì a được gọi là có thể áp

dụng được đối với trạng thái s

Áp dụng hành động a ở trạng thái s sẽ làm hệ thống chuyển đến

trạng thái s′∈ γ(s, a)

Các sự kiện: Thể hiện các chuyển trạng thái xảy ra ngẫu

nhiên

Nếu sự kiện e∈E và γ(s, no-op, e) ≠ ∅, thì e được gọi là có thể

xảy ra đối với trạng thái s

S

ự

xu

ấ

t hi

ệ

n (x

ả

y ra) s

ự

ki

ệ

n

e

ở

tr

ạ

ng thái

s

ẽ

làm h

ệ

th

ố

ng

chuyển đến trạng thái s′∈ γ(s, e)

Trí Tuệ Nhân Tạo

10

Kế hoạch và Mục tiêu

Kế hoạch (Plan): Là một cấu trúc (chuỗi có thứ tự) các

hành

độ

ng phù h

ợ

p c

ầ

n th

ự

c hi

ệ

n

để đạ

t

đượ

c m

ộ

t m

ụ

c

tiêu từ một trạng thái ban đầu

Các kiểu mục tiêu (Objective)

Trạng thái đích (goal state), hoặc một tập các trạng thái đích

Th

ỏ

a mãn m

ộ

t t

ậ

p các

đ

i

ề

u ki

ệ

n (conditions)

đố

i v

ớ

i chu

ỗ

i các

trạng thái đã duyệt qua

Tối ưu hóa một hàm tiện ích (utility function) được định nghĩa đối

với các trạng thái đã duyệt qua

Một nhiệm vụ (task) cần hoàn thành

Trí Tuệ Nhân Tạo

11

Lập kế hoạch và thực hiện

Bộ lập kế hoạch (Planner)

Mô tả của Σ

Đầu vào: Mô tả của hệ chuyển trạng

thái Σ, trạng thái đầu, mục tiêu

Trạng

thái đầu

Đầu ra: Kế hoạch để đạt được mục tiêu

đó

Planner

Kế hoạch

Controller

Hành động

Mục tiêu

Bộ điều khiển (Controller)

Đầu vào: Kế hoạch cần thực hiện, trạng

thái hiện thời (thông qua hàm quan sát

η: S→O, với O là tập các quan sát có thể)

Quan sát

Đầu ra: Hành động (tiếp theo) cần thực

hiện

System Σ

Sự kiện

Hệ chuyển trạng thái (State-

transition system)

Tiến triển tùy thuộc vào các hành động

được thực hiện và các sự kiện xảy ra

(http://www.inf.ed.ac.uk/teaching/

courses/plan/)

Trí Tuệ Nhân Tạo

12

Lập kế hoạch động (1)

Vấn đề: Thế giới thực tế có thể

Mô tả của Σ

khác với mô hình

đượ

c biểu diễn

bởi Σ

Sự khác biệt này cần phải được

x

ử

lý b

ở

i b

ộ đ

i

ể

u khi

ể

n (Controller)

Trạng

thái đầu

Planner

Mục tiêu

Kế hoạch

Controller

Hành động

System Σ

Sự kiện

Tình trạng thực

hiện

Mô hình thực tế: Kết hợp đan

xen giữa lập kế hoạch và thực

hiện

Quan sát

Giám sát kế hoạch (Plan

supervision): để phát hiện những

khi kết quả quan sát được khác

với mong muốn

(http://www.inf.ed.ac.uk/teaching/

courses/plan/)

Trí Tuệ Nhân Tạo

13

Lập kế hoạch động (2)

…

Mô tả của Σ

S

ử

a l

ạ

i k

ế

ho

ạ

ch (Plan revision)

:

để thay đổi thích nghi kế hoạch (đã

lập) theo những tình huống mới

Trạng

thái đầu

Planner

Mục tiêu

L

ậ

p l

ạ

i k

ế

ho

ạ

ch (Re-planning)

:

để

sinh ra kế hoạch mới từ trạng thái

hiện thời (hoặc từ trạng thái đầu)

Kế hoạch

Controller

Hành động

System Σ

Sự kiện

Tình trạng thực

hiện

Lập kế hoạch động (Dynamic

planning): Quá trình lặp lại giữa

bộ lập kế hoạch và bộ điều khiển

thực hiện

Quan sát

Tùy thuộc tình trạng của việc thực

hiện kế hoạch

(http://www.inf.ed.ac.uk/teaching/

courses/plan/)

Trí Tuệ Nhân Tạo

14

Giả thiết A0: Tập các trạng thái

Giả thiết A0: Tập các trạng thái (trong biểu diễn của Σ)

là h

ữ

u h

ạ

n

Nới lỏng điều kiện của giả thiết A0

Để

bi

ể

u di

ễ

n các hành

độ

ng t

ạ

o nên (làm xu

ấ

t hi

ệ

n) các

đố

i

tượng mới của bài toán

Để cho phép làm việc với các biến trạng thái kiểu số (numerical-

valued state variables) – ch

ứ

không ch

ỉ

v

ớ

i các bi

ế

n tr

ạ

ng thái

kiểu định danh (nominal-valued state variables)

Vấn đề gặp phải khi nới lỏng điều kiện của giả thiết A0

Khả năng quyết định được (decidability) và khả năng kết thúc

(termination) của các bộ lập kế hoạch sẽ không được bảo đảm

Trí Tuệ Nhân Tạo

15

Giả thiết A1: Quan sát đầy đủ

Giả thiết A1: Hệ thống có thể quan sát được đầy đủ (fully observable)

Planner và Controller có tri thức (quan sát) đầy đủ về trạng thái của thế giới

xung quanh

Hàm quan sát η cho phép xác định chính xác trạng thái tương ứng với

quan sát

Nới lỏng điều kiện của giả thiết A1

Để làm việc với các trạng thái mà trong đó các khía cạnh (của một trạng

thái) không được quan sát (nhận biết) đầy đủ

Ví dụ: Trong bài toán lập kế hoạch lộ trình có thể xảy ra tắc đường, thì

trạng thái của bài toán là không thể nhận biết (quan sát) được đầy đủ

Các vấn đề gặp phải khi nới lỏng điều kiện của giả thiết A1

Với hàm quan sát η: η(s)=o, thì η^-1(o) thường sẽ trả về nhiều hơn một trạng

thái có thể – vấn đề nhập nhằng

Các quan sát không hoàn toàn xác định được trạng thái hiện tại

Làm sao để xác định trạng thái tiếp theo là gì?

Trí Tuệ Nhân Tạo

16

Giả thiết A2: Chuyển trạng thái

Giả thiết A2: Kết quả của mỗi chuyển trạng thái là một trạng

thái xác

đị

nh (duy nhấ

t)

Với trạng thái s∈S, hành động a∈A, và sự kiện e∈E, thì không thể

xảy ra γ(s,a,e)={s’, s’’} (với s’, s’’ là 2 trạng thái khác nhau)

Nới lỏng điều kiện của giả thiết A2

Để lập kế hoạch cho các bài toán mà trong đó việc thực hiện một

hành động có thể đưa đến các kết quả khác nhau

Các vấn đề gặp phải khi nởi lỏng điều kiện của giả thiết A2

Controller phải quan sát được các kết quả thực tế của một hành

động

Kế hoạch được xây dựng có thể bao gồm thêm các thành phần

để xử lý với các hành động có nhiều kết quả

Trí Tuệ Nhân Tạo

17

Giả thiết A3: Các sự kiện

Giả thiết A3: Hệ thống là tĩnh, không có các sự kiện

(ng

ẫ

u nhiên) x

ả

y ra (

E

=

∅

)

Σ = (S,A,∅,γ); hay biểu diễn ngắn gọn là: (S,A,γ)

N

ớ

i l

ỏ

ng

đ

i

ề

u ki

ệ

n c

ủ

a gi

ả

thi

ế

t A3

Để biểu diễn (mô hình hóa) các bài toán lập kế hoạch trong đó có

xảy ra các sự kiện ngẫu nhiên

Vấn đề gặp phải khi nới lỏng điều kiện của giả thiết A3

Đối với Planner, thì môi trường hoạt động của hệ thống trở nên

không xác

đị

nh

Trí Tuệ Nhân Tạo

18

Giả thiết A4: Mục tiêu hạn chế

Giả thiết A4: Planner làm việc với một trạng thái đích,

ho

ặ

c v

ớ

i m

ộ

t t

ậ

p các tr

ạ

ng thái

đ

ích

Nới lỏng điều kiện của giả thiết A4

Để

l

ậ

p k

ế

ho

ạ

ch cho các bài toán mà trong

đ

ó m

ụ

c tiêu

đượ

c bi

ể

u

diễn bằng:

các ràng buộc đối với các trạng thái và kế hoạch, hoặc

hàm tiện ích, hoặc

nhiệm vụ cụ thể

V

ấ

n

đề

g

ặ

p ph

ả

i khi n

ớ

i l

ỏ

ng

đ

i

ề

u ki

ệ

n c

ủ

a gi

ả

thi

ế

t A4

Làm thế nào để biểu diễn và suy diễn đối với các ràng buộc, các

hàm tiện ích, và các nhiệm vụ?

Trí Tuệ Nhân Tạo

19

Giả thiết A5: Chuỗi hành động

Giả thiết A5: Một kế hoạch được xây dựng là một chuỗi hữu

h

ạ

n có thứ t

ự

của các hành

độ

ng

đượ

c th

ự

c hi

ệ

n liên tiếp nhau

Nới lỏng điều kiện của giả thiết A5

Để lập kế hoạch cho các bài toán trong đó có xảy ra các sự kiện

ngẫu nhiên (Xem giả thiết A3)

Để tạo nên các kiểu kế hoạch khác nhau (kế hoạch có điều kiện rẽ

nhánh, kế hoạch trong đó có những phần mà các hành động được

thực hiện không theo thứ tự,…)

Các vấn đề gặp phải khi nới lỏng điều kiện của giả thiết A5

Không được tạo thêm công việc (yêu cầu) đối với Controller

Suy diễn với các cấu trúc dữ liệu phức tạp hơn

Trí Tuệ Nhân Tạo

20

Bài giảng Trí tuệ nhân tạo - Chương 11: Lập kế hoạch - Nguyễn Nhật Quang