Giáo trình Trí tuệ nhân tạo (Artificial Intelligence) - Phạm Thọ Hoàn

Tài liệu giảng dạy Trí tuệ nhân tạo (ai) toàn tập [download pdf] hệ thống hóa kiến thức từ cơ bản đến nâng cao ngành tại Việt Nam

• Tác giả: Phạm Thọ Hoàn
• Trường học: Trường Đại học Sư phạm Hà Nội
• Chuyên ngành: Trí tuệ nhân tạo
• Đề tài: Giáo trình Trí tuệ nhân tạo
• Loại tài liệu: Giáo trình
• Năm xuất bản: 2011
• Địa điểm: Hà Nội

Tóm tắt

I. Giới thiệu về Trí tuệ nhân tạo và Tầm quan trọng

Trí tuệ nhân tạo (AI) là lĩnh vực khoa học máy tính tập trung vào việc tạo ra các hệ thống máy tính có khả năng thực hiện những công việc yêu cầu trí thông minh của con người. Kể từ khi những chiếc máy tính điện tử đầu tiên ra đời, các nhà khoa học đã hướng tới phát triển hệ thống thông minh có thể giải quyết các bài toán phức tạp một cách hiệu quả. Giáo trình Trí tuệ nhân tạo toàn tập được biên soạn bởi Phạm Thọ Hoàn và Phạm Thị Anh Lê từ Trường Đại học Sư phạm Hà Nội cung cấp nền tảng lý thuyết và thực tiễn vững chắc cho những ai muốn hiểu sâu về lĩnh vực này. Những thành tựu đáng kể của trí tuệ nhân tạo bao gồm hệ thống chơi cờ vua có thể thắng vua cờ thế giới và các phần mềm chứng minh hình học tự động.

1.1. Định nghĩa và khái niệm Trí tuệ nhân tạo

Trí tuệ nhân tạo là trí thông minh của máy do con người tạo ra, không nhất thiết phải bắt chước nguyên lý hoạt động của bộ não người. Giống như máy bay hiện đại bay tốt hơn chim mặc dù có cơ chế hoạt động khác biệt, AI cũng có thể vượt trội con người trong nhiều lĩnh vực cụ thể. Đánh giá sự thông minh của máy dựa trên kết quả thực hiện và hiệu suất công việc, chứ không phải nguyên lý hoạt động. Đây là một cách tiếp cận toàn diện về trí tuệ nhân tạo trong thực tiễn ứng dụng.

1.2. Các lĩnh vực chính của Trí tuệ nhân tạo

Giáo trình AI toàn tập bao gồm nhiều lĩnh vực quan trọng: tìm kiếm lời giải bài toán, lập luận logic, xử lý trò chơi trí tuệ, thỏa mãn ràng buộc, và học máy mạng nơron. Mỗi lĩnh vực cung cấp công cụ và phương pháp khác nhau để xây dựng hệ thống thông minh. Sự kết hợp các kỹ thuật này cho phép phát triển các ứng dụng AI phức tạp trong thực tiễn đời sống.

II. Phương pháp Tìm kiếm Lời giải trong Trí tuệ nhân tạo

Phương pháp tìm kiếm lời giải là nền tảng cơ bản trong giáo trình AI, cho phép máy tính tìm ra giải pháp tối ưu cho các bài toán phức tạp. Giáo trình trình bày nhiều giải thuật tìm kiếm khác nhau, từ tìm kiếm mù (blind search) đến tìm kiếm heuristic (heuristic search) có sử dụng thông tin phản hồi. Các giải thuật tìm kiếm này được đánh giá dựa trên tiêu chí như thời gian thực thi, không gian bộ nhớ, độ đầy đủ và hiệu suất tối ưu. Tìm hiểu sâu về các phương pháp tìm kiếm giúp nhà phát triển lựa chọn thuật toán phù hợp nhất cho từng bài toán cụ thể trong ứng dụng AI thực tế.

2.1. Giải thuật Tìm kiếm không có thông tin phản hồi

Tìm kiếm mù (blind search) là các giải thuật tìm kiếm không sử dụng thông tin hướng dẫn cụ thể về lời giải. Chúng bao gồm tìm kiếm chiều rộng, tìm kiếm chiều sâu, và tìm kiếm giới hạn độ sâu. Mặc dù đơn giản, những phương pháp tìm kiếm này rất hữu ích khi không có thông tin tiền định về hướng tìm kiếm. Độ hiệu quả của tìm kiếm mù phụ thuộc vào kích thước không gian tìm kiếm.

2.2. Giải thuật Tìm kiếm Heuristic

Giải thuật heuristic sử dụng thông tin phản hồi về bài toán để hướng dẫn quá trình tìm kiếm hiệu quả hơn. Tìm kiếm tốt nhất đầu tiên (best first search) là một kỹ thuật phổ biến, với các biến thể nổi tiếng là tìm kiếm A* và tìm kiếm A tham lam. Những giải thuật heuristic này thường nhanh hơn tìm kiếm mù và tiêu tốn ít tài nguyên hơn khi giải quyết các bài toán phức tạp.

III. Lập luận Logic và Suy diễn trong Trí tuệ nhân tạo

Lập luận logic là công cụ quan trọng để biểu diễn và xử lý tri thức trong hệ thống AI. Giáo trình AI toàn tập giới thiệu chi tiết hai hệ thống logic chính: logic mệnh đề và logic vị từ cấp một. Logic mệnh đề cung cấp nền tảng cơ bản với cú pháp và ngữ nghĩa rõ ràng, cho phép biểu diễn các sự kiện đơn giản. Logic vị từ cấp một (first-order logic) mạnh mẽ hơn, cho phép mô tả các quan hệ phức tạp giữa các đối tượng. Các thuật toán suy diễn như phân giải (resolution), suy diễn tiến (forward chaining), và suy diễn lùi (backward chaining) giúp máy tính rút ra kết luận từ các tri thức đã biết, tạo nên cơ sở cho các hệ thống chuyên gia.

3.1. Logic mệnh đề và Suy diễn cơ bản

Logic mệnh đề biểu diễn tri thức thông qua các mệnh đề (phát biểu đúng hoặc sai). Luật phân giải là phương pháp suy diễn mạnh mẽ trong logic mệnh đề, cho phép loại bỏ các mâu thuẫn và rút ra kết luận. Câu dạng Horn là trường hợp đặc biệt giúp suy diễn hiệu quả hơn. Các thuật toán suy diễn trên logic mệnh đề tạo nền tảng cho những hệ thống suy luận phức tạp hơn.

3.2. Logic vị từ cấp một và Ứng dụng

Logic cấp một cho phép biểu diễn tri thức với vị từ và biến, tạo sự linh hoạt cao trong mô hình hóa bài toán. Phép đồng nhất (unification) là kỹ thuật cốt lõi giúp so sánh và liên kết các vị từ khác nhau. Luật phân giải tổng quát mở rộng khả năng suy diễn từ logic mệnh đề lên logic cấp một. Những công cụ này là nền tảng cho lập trình logic và ngôn ngữ Prolog.

IV. Lập trình Logic và Ứng dụng Thực tiễn

Lập trình logic (logic programming) là một paradigm lập trình dựa trên logic cấp một, cho phép biểu diễn bài toán theo cách khai báo thay vì mệnh lệnh. Ngôn ngữ Prolog là ngôn ngữ lập trình logic nổi tiếng nhất, được sử dụng rộng rãi trong các hệ thống AI và xử lý ngôn ngữ tự nhiên. Giáo trình AI chi tiết cách hoạt động của Prolog, bao gồm cách trả lời truy vấn, cơ chế quay lui (backtracking), và cắt tỉa (cut) để tối ưu hóa tìm kiếm. Vị từ đệ qui (recursive predicates) trong Prolog cho phép giải quyết các bài toán với cấu trúc dữ liệu phức tạp. Môi trường lập trình SWI Prolog cung cấp các công cụ thực tiễn để phát triển các ứng dụng logic hiệu quả.

4.1. Cơ chế hoạt động của Ngôn ngữ Prolog

Prolog sử dụng suy diễn lùi (backward chaining) để trả lời truy vấn bằng cách tìm kiếm trong cơ sở tri thức. Cơ chế quay lui tự động tìm kiếm các lời giải thay thế khi gặp thất bại. Cắt tỉa giúp loại bỏ các nhánh tìm kiếm không cần thiết, tăng hiệu suất. Vị từ phi logic mở rộng khả năng của Prolog vượt ngoài logic thuần túy. Sự kết hợp này làm cho Prolog rất linh hoạt cho lập trình AI.

4.2. Cấu trúc dữ liệu và Ứng dụng trong Prolog

Prolog hỗ trợ các cấu trúc dữ liệu như danh sách, cây, và các cấu trúc phức hợp khác. Vị từ đệ qui giúp xử lý các cấu trúc dữ liệu phân cấp một cách tự nhiên. Môi trường SWI Prolog cung cấp thư viện phong phú hỗ trợ xây dựng các ứng dụng từ tìm kiếm đơn giản đến các hệ thống chuyên gia phức tạp. Lập trình logic trong Prolog được ứng dụng rộng rãi trong xử lý tri thức.

Trích đoạn nội dung tài liệu

Chương 1. Giới thiệu: trình bày tổng quan về AI, lịch sử ra đời và phát triển và các lính vực ứng dụng của AI. Các phương pháp tìm kiếm lời giải: trình bày các kỹ thuật tìm kiếm cơ bản được áp dụng để giải quyết các vấn đề và được áp dụng rộng rãi trong các lĩnh vực của trí tuệ nhân tạo. Các giải thuật tìm kiếm lời giải cho trò chơi: trình bày một số kỹ thuật tìm kiếm trong các trò chơi có đối thủ.

Các phương pháp lập luận trên logic mệnh đề: trình bày cú pháp, ngữ nghĩa của logic mệnh đề và một số thuật toán lập luận trên logic mệnh đề. Các phương pháp lập luận trên logic vị từ cấp một: trình bày cú pháp, ngữ nghĩa của logic vị từ cấp một và một số thuật toán lập luận cơ bản trên logic vị từ cấp một. Prolog: Giới thiệu chung về ngôn ngữ Prolog, cú pháp, ngữ nghĩa và cấu trúc chương trình trong Prolog, một số phiên bản mới của Prolog như SWI Prolog,… Chương 7. Lập luận với tri thức không chắc chắn: Giới thiệu về tri thức không chắc chắn và một số cách tiếp cận biểu diễn và xử lý tri thức không chắc chắn.

Học mạng noron nhân tạo: Giới thiệu về phương pháp và các kỹ thuật cơ bản trong lập luận sử dụng mạng noron nhân tạo. Chương 2 – Bài toán và phương pháp tìm kiếm lời giải 1. Bài toán và các thành phần của bài toán Chương này giới thiệu các giải thuật máy tính có thể giải các bài toán mà thông thường đòi hỏi trí thông minh của con người, như bài toán đong nước, bài toán 8 sô trên bàn cờ, bài toán tìm đường như mô tả bên dưới đây. Để thiết kế giải thuật chung giải các bài toán này, chúng ta nên phát biểu bài toán theo dạng 5 thành phần: Trạng thái bài toán, trạng thái đầu, trạng thái đích, các phép chuyển trạng thái, lược đồ chi phí các phép chuyển trạng thái (viết gọn là chi phí).

Bài toán đong nước 9l 3l 5l Sử dụng ba can 3 lít, 5 lít và 9 lít, làm thế nào để đong được 7 lít nước. Bài toán này được phát biểu lại theo 5 thành phần như sau: - Trạng thái: Gọi số nước có trong 3 can lần lượt là a, b, c (a ≤ 3, b ≤ 5, c ≤ 9), khi đó bộ ba (a, b, c) là trạng thái của bài toán - Trạng thái đầu: (0, 0, 0) // cả ba can đều rỗng - Trạng thái đích (-, -, 7) // can thứ 3 chứa 7 lít nước - Phép chuyển trạng thái: từ trạng thái (a,b,c) có thể chuyển sang trạng thái (x,y,z) thông qua các thao tác như làm rỗng 1 can, chuyển từ can này sang can kia đến khi hết nước ở can nguồn hoặc can đích bị đầy. - Chi phí mỗi phép chuyển trạng thái: mỗi phép chuyển trạng thái có chi phí là 1. Một lời giải của bài toán là một dãy các phép chuyển trạng thái (đường đi) từ trạng thái đầu đến trạng thái đích.

Bảng dưới đây là 2 lời giải của bài toán trên: a b c  Đầu  a b c 0 0 0 0 0 0 3 0 0 0 5 0 0 0 3 3 2 0 3 0 3 3 0 2 0 0 6 3 5 2 3 0 6 Đích  3 0 7 0 3 6 Lời giải 2 (chi phí: 5) 3 3 6 1 5 6 0 5 7  Đích Lời giải 1 (chi phí: 9) b. Bài toán di chuyển 8 số trên bàn cờ Trạng thái đầu Trạng thái đích Cho bàn cờ kích thước 3 x 3, trên bàn cờ có 8 quân cờ đánh số từ 1 đến 8 (hình vẽ). Trên bàn cờ có một ô trống. Chúng ta có thể chuyển một quân cờ có chung cạnh với ô trống sang ô trống.

Hãy tìm dãy các phép chuyển để từ trạng thái ban đầu về trạng thái mà các quan cờ được xếp theo trật tự như Trạng thái đích của hình trên. Bài toán di chuyển 8 số trên bàn cờ có thể phát biểu dưới dạng 5 thành phần như sau: - Biểu diễn trạng thái: mảng 2 chiều kích thước 3x3, phần tử của mảng lưu số hiệu quân cờ (từ 0 đến 9, 0 là vị trí trống). Cũng có thể biểu diễn trạng thái bàn cờ bằng mảng một chiều gồm 9 phần tử: ba phần tử đầu tiên biểu diễn các ô thuộc dòng đầu tiên của bàn cờ, ba phần tử tiếp biểu diễn các quân cờ thuộc dòng thứ hai, ba phần tử cuối cùng biểu diễn các quân cờ thuộc dòng cuối cùng. Ở đây chúng tôi sử dụng mảng hai chiều 3x3 để cho giống với bàn cờ trên thực tế.

- Trạng thái đầu (hình vẽ trên) - Trạng thái đích (hình vẽ trên) - Phép chuyển trạng thái: đổi chỗ ô có số hiệu 0 với một trong các ô có cùng cạnh. - Chi phí: mỗi phép chuyển có chi phí 1. Lời giải của bài toán là dãy các phép chuyển từ trạng thái đầu đến trạng thái đích. Một lời giải của bài toán là: UP, UP, RIGHT, DOWN, LEFT, UP, RIGHT, RIGHT, DOWN, LEFT, LEFT, UP, RIGHT, DOWN, RIGHT, DOWN (chú ý: up, down, right, left là biểu diễn sự dịch chuyển ô trống lên trên, xuống dưới, sang phải, sang trái) c.

Bài toán tìm đường đi Một ôtô robot tìm đường đi từ thành phố Arad đến thành phố Bucharest. Biết rằng xe robot này không có bản đồ đầy đủ như trên hình vẽ trên, nhưng khi nó đến một thành phố mới, nó có bộ cảm biến đọc được biển chỉ đường đến các thành lân cận, trên biển chỉ đường có khoảng cách. Bài toán tìm đường có thể phát biểu theo 5 thành phần như sau: - Trạng thái: vị trí của ôtô robot (tên thành phố) - Trạng thái đầu: Thành phố Arad - Trạng thái đích: Thành phố Bucharest - Phép chuyển trạng thái: từ thành phố sang thành phố lân cận - Chi phí: khoảng cách giữa 2 thành phố trong phép chuyển trạng thái Lời giải của bài toán là dãy các phép chuyển từ trạng thái đầu đến trạng thái đích, hay là đường đi từ thành phố đầu đến thành phố đích. Một ví dụ của lời giải bài toán là: Arad  Sibiu  Fagaras  Bucharest.

Giải thuật tổng quát tìm kiếm lời giải a. Không gian trạng thái của bài toán Mỗi bài toán với 5 thành phần như mô tả ở trên, chúng ta có thể xây dựng được một cấu trúc đồ thị với các nút là các trạng thái của bài toán, các cung là phép chuyển trạng thái. Đồ thị này được gọi là không gian trạng thái của bài toán. Không gian trạng thái có thể là vô hạn hoặc hữu hạn.

Ví dụ, với bài toán di chuyển 8 số trên bàn cờ, không gian trạng thái có số lượng là 8! (8 giai thừa) trạng thái. Lời giải của bài toán là một đường đi trong không gian trạng thái có điểm đầu là trạng thái đầu và điểm cuối là trạng thái đích. Nếu không gian trạng thái của bài toán là nhỏ, có thể liệt kê và lưu vừa trong bộ nhớ của máy tính thì việc tìm đường đi trong không gian trạng thái có thể áp dụng các thuật toán tìm đường đi trong lý thuyết đồ thị. Tuy nhiên, trong rất nhiều trường hợp, không gian trạng thái của bài toán là rất lớn, việc duyệt toàn bộ không gian trạng thái là không thể.

Trong môn học Trí tuệ nhân tạo này, chúng ta sẽ tìm hiểu các phương pháp tìm kiếm lời giải trong các bài toán có không gian trạng thái lớn. Giải thuật tổng quát tìm kiếm lời giải của bài toán Với các bài toán có 5 thành phần ở trên, chúng ta có giải thuật chung để tìm kiếm lời giải của bài toán. Ý tưởng là sinh ra các lời giải tiềm năng và kiểm tra chúng có phải là lời giải thực sự của bài toán. Một lời giải tiềm năng là một đường đi trong không gian trạng thái của bài toán có nút đầu là trạng thái đầu và mỗi cung của đường đi là một phép chuyển hợp lệ giữa các trạng thái kề với cung đó.

Lời giải thực sự của bài toán là lời giải tiềm năng có nút cuối cùng là trạng thái đích. Các lời giải tiềm năng là các đường đi có cùng nút đầu tiên và dãy các cung là dãy các phép chuyển hợp lệ từ trạng thái đầu đó. Các lời giải tiềm năng có thể tổ chức theo cây, gốc của cây là trạng thái đầu, cây được phát triển bằng cách bổ sung vào các nút liền kề với trạng thái đầu, sau đó liên tiếp bổ sung vào các con của các nút lá, … Lược đồ chung để tìm lời giải của bài toán 4 thành phần trên là xây dựng cây lời giải tiểm năng (hay là cây tìm kiếm) và kiểm tra lời giải tiềm năng có là lời giải thực sự của bài toán hay không. Các bước của giải thuật chung là như sau: xây dựng cây tìm kiếm mà nút gốc là trạng thái đầu, lặp lại 2 bước: kiểm tra xem trạng thái đang xét có là trạng thái đích không, nếu là trạng thái đích thì thông báo lời giải, nếu không thì mở rộng cây tìm kiếm bằng cách bổ sung các nút con là các trạng thái láng giềng của trạng thái đang xét.

Giải thuật chung được trình bày trong bảng sau: Đầu vào của giải thuật là bài toán (problem) với 5 thành phần (biểu diễn trạng thái tổng quát, trạng thái đầu, trạng thái đích, phép chuyển trạng thái, chi phí phép chuyển trạng thái) và một chiến lược tìm kiếm (strategy); đầu ra của giải thuật là một lời giải của bài toán hoặc giá trị failure nếu bài toán không có lời giải. Giải thuật sinh ra cây các lời giải tiềm năng, nút gốc là trạng thái đầu của bài toán, mở rộng cây theo chiến lược (strategy) đã định trước đến khi cây chứa nút trạng thái đích hoặc không thể mở rộng cây được nữa. Function General_Search(problem, strategy) returns a solution, or failure cây-tìm-kiếm  trạng-thái-đầu; while (1) { if (cây-tìm-kiếm không thể mở rộng được nữa) then return failure nút-lá  Chọn-1-nút-lá(cây-tìm-kiếm, strategy) if (node-lá là trạng-thái-đích) then return Đường-đi(trạng-thái-đầu, nút- lá) else mở-rộng(cây-tìm-kiếm, các-trạng-thái-kề(nút-lá)) } Trong giải thuật chung này, chiến lược tìm kiếm (strategy) sẽ quyết định việc chọn nút lá nào trong số nút lá của cây để mở rộng cây tìm kiếm, ví dụ như nút lá nào xuất hiện trong cây sớm hơn thì được chọn trước để phát triển cây (đây là chiến lược tìm kiếm theo chiều rộng), hoặc nút lá nào xuất hiện sau thì được chọn để mở rộng cây (đây là chiến lược tìm kiếm theo chiều sâu). Chiến lược tìm kiếm có thể được cài đặt thông qua một cấu trúc dữ liệu để đưa vào và lấy ra trạng thái lá của cây tìm kiếm.

Hai cấu trúc dữ liệu cơ bản là hàng đợi và ngăn xếp.