Bài giảng Trí tuệ nhân tạo - Bài 3: Giải quyết vấn đề. Tìm kiếm

Trí Tuệ Nhân Tạo

(Artificial Intelligence)

Thân Quang Khoát

[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 2020

Nội dung môn học:

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

n Tác tử

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

q Các chiến lược tìm kiếm cơ bản (Uninformed search)

n Logic và suy diễn

n Biểu diễn tri thức

n Học máy

Trí tuệ nhân tạo

2

Giải quyết vấn đề bằng tìm kiếm

n Giải quyết vấn đề bằng tìm kiếm

q Tìm chuỗi các hành động cho phép đạt đến (các) trạng thái mong muốn

n Các bước chính

q Xác định mục tiêu cần đạt đến (goal formulation)

n Là một tập hợp của các trạng thái (đích)

n Dựa trên: trạng thái hiện tại (của môi trường) và đánh giá hiệu quả hành động

(của tác tử)

q Phát biểu bài toán (problem formulation)

n Với một mục tiêu, xác định các hành động và trạng thái cần xem xét

q Quá trình tìm kiếm (search process)

n Xem xét các chuỗi hành động có thể

n Chọn chuỗi hành động tốt nhất

n Giải thuật tìm kiếm

q Đầu vào: một bài toán (cần giải quyết)

q Đầu ra: một giải pháp, dưới dạng một chuỗi các hành động cần thực hiện

Trí tuệ nhân tạo

3

Tác tử giải quyết vấn đề

Trí tuệ nhân tạo

4

Giải quyết vấn đề bằng tìm kiếm

n Một người du lịch đang trong chuyến đi du lịch ở Rumani

q Anh ta hiện thời đang ở Arad

q Ngày mai, anh ta có chuyến bay khởi hành từ Bucharest

q Bây giờ, anh ta cần di chuyển (lái xe) từ Arad đến Bucharest

n Phát biểu mục tiêu:

q Cần phải có mặt ở Bucharest

n Phát biểu bài toán:

q Các trạng thái: các thành phố (đi qua)

q Các hành động: lái xe giữa các thành phố

n Tìm kiếm giải pháp:

q Chuỗi các thành phố cần đi qua, ví dụ: Arad, Sibiu, Fagaras,

Bucharest

Trí tuệ nhân tạo

5

Giải quyết vấn đề bằng tìm kiếm

Trí tuệ nhân tạo

6

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

n Xác định, có thể quan sát hoàn toàn à Bài toán trạng thái

đơn

q Tác tử biết chính xác trạng thái tiếp theo mà nó sẽ chuyển qua

q Giải pháp của bài toán: một chuỗi hành động

n Không quan sát được à Bài toán thiếu cảm nhận

q Tác tử có thể không biết là nó đang ở trạng thái nào

q Giải pháp của bài toán: một chuỗi hành động

n Không xác định và/hoặc có thể quan sát một phần à Bài

toán có sự kiện ngẫu nhiên

q Các nhận thức cung cấp các thông tin mới về trạng thái hiện tại

q Giải pháp của bài toán: một kế hoạch (chính sách)

q Thường kết hợp đan xen giữa: tìm kiếm và thực hiện

n Không biết về không gian trạng thái à Bài toán thăm dò

Trí tuệ nhân tạo

7

Ví dụ: Bài toán máy hút bụi (1)

n Nếu là bài toán trạng thái

đơn

q Bắt đầu ở trạng thái #5.

n Giải pháp?

Trí tuệ nhân tạo

8

Ví dụ: Bài toán máy hút bụi (2)

n Nếu là bài toán trạng thái

đơn

q Bắt đầu ở trạng thái #5.

n Giải pháp?

q [Sang phải, Hút bụi]

Trí tuệ nhân tạo

9

Ví dụ: Bài toán máy hút bụi (3)

n Nếu là bài toán thiếu cảm

nhận

q Bắt đầu (có thể) ở trạng thái

{#1,#2,#3,#4,#5,#6,#7,#8}

q Luôn bắt đầu bằng di chuyển

sang phải

n Giải pháp?

Trí tuệ nhân tạo

10

Ví dụ: Bài toán máy hút bụi (4)

n Nếu là bài toán thiếu cảm

nhận

q Bắt đầu (có thể) ở trạng thái

{#1,#2,#3,#4,#5,#6,#7,#8}

q Luôn bắt đầu bằng di chuyển

sang phải

n Giải pháp?

q [Sang phải, Hút bụi, Sang trái,

Hút bụi]

Trí tuệ nhân tạo

11

Ví dụ: Bài toán máy hút bụi (5)

n Nếu là bài toán có sự kiện

ngẫu nhiên

q Bắt đầu ở trạng thái #5

q Không xác định: Hút bụi có thể

làm bẩn một cái thảm sạch!

q Có thể quan sát một phần: vị

trí, mức độ bẩn ở vị trí hiện

thời

n Giải pháp?

Trí tuệ nhân tạo

12

Ví dụ: Bài toán máy hút bụi (6)

n Nếu là bài toán có sự kiện

ngẫu nhiên

q Bắt đầu ở trạng thái #5

q Không xác định: Hút bụi có thể

làm bẩn một cái thảm sạch!

q Có thể quan sát một phần: vị

trí, mức độ bẩn ở vị trí hiện

thời

n Giải pháp?

q [Sang phải, if Bẩn then Hút

bụi]

Trí tuệ nhân tạo

13

Phát biểu bài toán trạng thái đơn

Bài toán được định nghĩa bởi 4 thành phần:

n Trạng thái đầu

q Ví dụ: “đang ở thành phố Arad“

n Các hành động – Xác định bởi hàm chuyển trạng thái:

S(trạng_thái_hiện_thời) = tập các cặp <hành_động, trạng_thái_tiếp_theo>

q Ví dụ: S(Arad) = {<Arad à Zerind, Zerind>, … }

n Kiểm tra mục tiêu, có thể là

q Trực tiếp – ví dụ: Trạng thái hiện thời x = “Đang ở thành phố Bucharest"

q Gián tiếp – ví dụ: HếtCờ(x), Sạch(x), …

n Chi phí đường đi (giải pháp)

q Ví dụ: Tổng các khoảng cách, Số lượng các hành động phải thực hiện,…

q c(x,a,y) ≥ 0 là chi phí bước (bộ phận) – chi phí cho việc áp dụng hành

động a để chuyển từ trạng thái x sang trạng thái y

n Một giải pháp: Một chuỗi các hành động cho phép dẫn từ trạng thái

đầu đến trạng thái đích

Trí tuệ nhân tạo

14

Xác định không gian trạng thái

n Các bài toán thực tế thường được mô tả phức tạp

à Không gian trạng thái cần được khái quát (abstracted) để phục

vụ cho việc giải quyết bài toán

n Trạng thái (khái quát) = Một tập các trạng thái thực tế

n Hành động (khái quát) = Một kết hợp phức tạp của các hành

động thực tế

q Ví dụ: Hành động "Arad à Zerind" biểu diễn một tập kết hợp các

đường, đường vòng, chỗ nghỉ, …

n Để đảm bảo việc thực hiện (quá trình tìm kiếm), bất kỳ trạng

thái thực tế nào cũng phải có thể đạt đến được từ trạng thái

thực tế khác

n Giải pháp (khái quát) = Một tập các đường đi giải pháp trong

thực tế

Trí tuệ nhân tạo

15

Đồ thị không gian trạng thái (1)

Bài

toán

máy

hút

bụi

n Các trạng thái?

n Các hành động?

n Kiểm tra mục tiêu?

n Chi phí đường đi?

Trí tuệ nhân tạo

16

Đồ thị không gian trạng thái (2)

Bài

toán

máy

hút

bụi

n Các trạng thái?

n Các hành động?

Chỗ bẩn và vị trí máy hút bụi

Sang trái, sang phải, hút bụi, không làm gì

n Kiểm tra mục tiêu? Không còn chỗ (vị trí) nào bẩn

n Chi phí đường đi? 1 (mỗi hành động), 0 (không làm gì cả)

Trí tuệ nhân tạo

17

Biểu diễn bằng cây và đồ thị

B là cha của C

C là con của B

A là tổ tiên của C

C là con cháu của A

Trí tuệ nhân tạo

18

Đồ thị tìm kiếm ® Cây tìm kiếm

n Các bài toán tìm kiếm trên đồ thị có thể được chuyển

thành các bài toán tìm kiếm trên cây

q Thay thế mỗi liên kết (cạnh) vô hướng bằng 2 liên kết (cạnh) có

hướng

q Loại bỏ các vòng lặp tồn tại trong đồ thị (để tránh không duyệt 2

lần đối với một nút trong bất kỳ đường đi nào)

Trí tuệ nhân tạo

19

Các giải thuật tìm kiếm theo cấu trúc cây

n₀

n Ý tưởng:

q Khám phá (xét) không gian trạng thái

bằng cách sinh ra các trạng thái kế tiếp

của các trạng thái đã khám phá (đã xét)

n

q Còn gọi là phương pháp khai triển (phát

triển) các trạng thái

successors(n)

Goal

Trí tuệ nhân tạo

20

Bài giảng Trí tuệ nhân tạo - Bài 3: Giải quyết vấn đề. Tìm kiếm - Thân Quang Khoát