Bài giảng Trí tuệ nhân tạo - Chương 3: Thuật toán - Thuật giải - Đào Nam Anh

1Artificial Intelligence Trí Tuệ Nhân tạo TS. Đào Nam Anh THUẬT TOÁN – THUẬT GIẢI 2Tài liệu Stuart Russell and Peter Norvig, Artificial Intelligence - A Modern Approach R. E. Bellman. An Introduction to Artificial Intelligence: Can Computers Think? Boyd & Fraser Publishing Company, San Francisco, 1978. E. Charniak and D. McDermott. Introduction to Artificial Intelligence. Addison- Wesley,Reading, Massachusetts, 1985. J. Haugeland. Artificial Intelligence: The Very Idea. MIT Press, Cambridge, Massachusetts, 1985. R. Kurzweil. The Age of Intelligent Machines. MIT Press, Cambridge, Massachusetts, 1990. N. J. Nilsson. Artificial Intelligence: A New Synthesis. Morgan Kaufmann, San Mateo, California, 1998. D. Poole, A. K. Mackworth, and R. Goebel. Computational Intelligence: A Logical Approach. Oxford University Press, Oxford, UK, 1998. E. Rich and K. Knight. Artificial Intelligence (Second Edition). McGraw-Hill, New York, 1991. P. H. Winston. Artificial Intelligence (Third Edition). Addison-Wesley, Reading, Massachusetts, 1992. N.Q.Hoan, Nhập môn trí tuệ nhân tạo Đinh Mạnh Tường, Giáo trình Trí tuệ Nhân tạo Hoàng Kiếm, Đinh Nguyễn Anh Dũng, Giáo trình Nhập môn Trí tuệ Nhân tạo 3NỘI DUNG I. KHÁI NIỆM THUẬT TOÁN – THUẬT GIẢI II. THUẬT GIẢI HEURISTIC III. TÁC TỬ IV. GIẢI QUYẾT BÀI TOÁN BẰNG CÁCH TÌM KIẾM V. CÁC PHƯƠNG PHÁP TÌM KIẾM THIẾU THÔNG TIN VI. CÁC PHƯƠNG PHÁP TÌM KIẾM HEURISTIC 4KHÁI NIỆM THUẬT TOÁN – THUẬT GIẢI Trong quá trình nghiên cứu giải quyết các vấn đề – bài toán: Có nhiều bài toán cho đến nay vẫn chưa tìm ra một cách giải theo kiểu thuật toán và cũng không biết là có tồn tại thuật toán hay không. Có nhiều bài toán đã có thuật toán để giải nhưng không chấp nhận được vì thời gian giải theo thuật toán đó quá lớn hoặc các điều kiện cho thuật toán khó đáp ứng. Có những bài toán được giải theo những cách giải vi phạm thuật toán nhưng vẫn chấp nhận được. 5KHÁI NIỆM THUẬT TOÁN – THUẬT GIẢI Cần phải có những đổi mới cho khái niệm thuật toán:mở rộng hai tiêu chuẩn của thuật toán: tính xác định và tính đúng đắn. Mở rộng Tính xác định: các giải thuật đệ quy và ngẫu nhiên. Tính đúng của thuật toán: không còn bắt buộc đối với một số cách giải bài toán, nhất là các cách giải gần đúng. Một trong những thuật giải thường được đề cập đến và sử dụng trong khoa học trí tuệ nhân tạo là các cách giải theo kiểu Heuristic 6THUẬT GIẢI HEURISTIC Thuật giải Heuristic là một sự mở rộng khái niệm thuật toán. Thường tìm được lời giải tốt (nhưng không chắc là lời giải tốt nhất) Giải bài toán theo thuật giải Heuristic thường dễ dàng và nhanh chóng đưa ra kết quả hơn so với giải thuật tối ưu, vì vậy chi phí thấp hơn. Thuật giải Heuristic thường thể hiện khá tự nhiên, gần gũi với cách suy nghĩ và hành động của con người. 7THUẬT GIẢI HEURISTIC Phương pháp xây dựng một thuật giải Heuristic Nguyên lý vét cạn thông minh: Trong một bài toán tìm kiếm nào đó, khi không gian tìm kiếm lớn, ta thường tìm cách giới hạn lại không gian tìm kiếm hoặc thực hiện một kiểu dò tìm đặc biệt dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêu. Nguyên lý tham lam (Greedy): Lấy tiêu chuẩn tối ưu (trên phạm vi toàn cục) của bài toán để làm tiêu chuẩn chọn lựa hành động cho phạm vi cục bộ của từng bước (hay từng giai đoạn) trong quá trình tìm kiếm lời giải. Nguyên lý thứ tự: Thực hiện hành động dựa trên một cấu trúc thứ tự hợp lý của không gian khảo sát nhằm nhanh chóng đạt được một lời giải tốt. 8THUẬT GIẢI HEURISTIC Phương pháp xây dựng một thuật giải Heuristic Hàm Heuristic: Đó là các hàm đánh giá thô, giá trị của hàm phụ thuộc vào trạng thái hiện tại của bài toán tại mỗi bước giải. Nhờ giá trị này, ta có thể chọn được cách hành động tương đối hợp lý trong từng bước của thuật giải. 9Bài toán: Hãy tìm một hành trình cho một người giao hàng đi qua n điểm khác nhau, mỗi điểm đi qua một lần và trở về điểm xuất phát sao cho tổng chiều dài đoạn đường cần đi là ngắn nhất. Giả sử rằng có con đường nối trực tiếp từ giữa hai điểm bất kỳ. Cách liệt kê tất cả con đường có thể đi, tính chiều dài của mỗi con đường đó rồi tìm con đường có chiều dài ngắn nhất. độ phức tạp 0(n!), khi số đại lý tăng thì số con đường phải xét sẽ tăng lên rất nhanh. Thuật giải Heuristic ứng dụng nguyên lý Greedy: – Từ điểm khởi đầu, ta liệt kê tất cả quãng đường từ điểm xuất phát cho đến n đại lý rồi chọn đi theo con đường ngắn nhất. – Khi đã đi đến một đại lý, chọn đi đến đại lý kế tiếp cũng theo nguyên tắc trên. Nghĩa là liệt kê tất cả con đường từ đại lý ta đang đứng đến những đại lý chưa đi đến. Chọn con đường ngắn nhất. Lặp lại quá trình này cho đến lúc không còn đại lý nào để đi. THUẬT GIẢI HEURISTIC Phương pháp xây dựng một thuật giải Heuristic Bài toán hành trình ngắn nhất – ứng dụng nguyên lý Greedy 10 THUẬT GIẢI HEURISTIC Phương pháp xây dựng một thuật giải Heuristic Bài toán hành trình ngắn nhất – ứng dụng nguyên lý Greedy 11 THUẬT GIẢI HEURISTIC Phương pháp xây dựng một thuật giải Heuristic Bài toán hành trình ngắn nhất – ứng dụng nguyên lý Greedy Thuật giải theo kiểu Heuristic đôi lúc lại đưa ra kết quả không tốt, như trường hợp ở hình sau. 12 THUẬT GIẢI HEURISTIC Phương pháp xây dựng một thuật giải Heuristic Bài toán phân việc – ứng dụng của nguyên lý thứ tự Một công ty nhận được hợp đồng gia công m chi tiết máy J1, J2, Jm. Công ty có n máy gia công lần lượt là P1, P2, Pn. Mọi chi tiết đều có thể được gia công trên bất kỳ máy nào. Một khi đã gia công một chi tiết trên một máy, công việ sẽ tiếp tục cho đến lúc hoàn thành, không thể bị cắt ngang. Để gia công một việc J1 trên một máy bất kỳ ta cần dùng một thời gian tương ứng là t1. Nhiệm vụ của công ty là phải làm sao gia công xong toàn bộ n chi tiết trong thời gian sớm nhất. 13 THUẬT GIẢI HEURISTIC Phương pháp xây dựng một thuật giải Heuristic Bài toán hành trình ngắn nhất – ứng dụng nguyên lý Greedy Xét bài toán trong trường hợp có 3 máy P1, P2, P3 và 6 công việc với thời gian là t1=2, t2=5, t3=8, t4=1, t5=5, t6=1. Có một phương án phân công (L) như hình sau: Sơ đồ phân việc theo hình ở trên được gọi là lược đồ GANTT. Thời gian để hoàn thành toàn bộ 6 công việc là 12. Phương án (L) vừa thực hiện là một phương án không tốt. Các máy P1 và P2 có quá nhiều thời gian rãnh. 14 THUẬT GIẢI HEURISTIC Phương pháp xây dựng một thuật giải Heuristic Bài toán hành trình ngắn nhất – ứng dụng nguyên lý Greedy Thuật toán tìm phương án tối ưu L0 cho bài toán này theo kiểu vét cạn có độ phức tạp cỡ O(mn) (với m là số máy và n là số công việc). Một thuật giải Heuristic rất đơn giản (độ phức tạp O(n)) để giải bài toán này: – Sắp xếp các công việc theo thứ tự giảm dần về thời gian gia công. – Lần lượt sắp xếp các việc theo thứ tự đó vào máy còn dư nhiều thời gian nhất. – Có một phương án L* như sau: – Phương án L* là phương án tối ưu: thời gian hoàn thành là 8, đúng bằng thời gian của công việc J3. 15 THUẬT GIẢI HEURISTIC Phương pháp xây dựng một thuật giải Heuristic Bài toán hành trình ngắn nhất – ứng dụng nguyên lý Greedy Một giải Heuristic đơn giản như vậy sẽ là một thuật giải tối ưu? Không, dễ dàng đưa ra được kết quả tối ưu hơn kết quả trên. 16 AI Agents/Tác tử - Định nghĩa An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators Human agent: eyes, ears, and other organs for sensors; Hands, legs, mouth, and other body parts for actuators Robotic agent: cameras and infrared range finders for sensors; various motors for actuators Tác tử là bất cứ cái gì (con người, người máy, software robots, các bộ ổn nhiệt,) có khả năng cảm nhận môi trường xung quanh nó thông qua các bộ phận cảm biến và hành động phù hợp theo môi trường đó thông qua các bộ phận hoạt động Tác tử con người; Các bộ phận cảm biến: mắt, tai, và một số bộ phận cơ thể khác Các bộ phận hoạt động: tay, chân, miệng, và một số bộ phận cơ thể khác Tác tử người máy: Các bộ phận cảm biến: các máy quay (cameras), các bộ truy tìmtín hiệu hồng ngoại Các bộ phận hoạt động: các loại động cơ (motors) 17 Examples of Agents Ví dụ về tác tử Humans Programs Robots___ senses keyboard, mouse, dataset cameras, pads body parts monitor, speakers, files motors, limbs 18 Agents and environments Tác tử và Môi trường The agent function maps from percept histories to actions:/ Hàm tác tử: là hàm ánh xạ từ lịch sử nhận thức tới các hành động [f: P*
A] The agent program runs on the physical architecture to produce f /Chương trình tác tử: hoạt động (chạy) dựa trên kiến trúc thực tế của hàm f agent = architecture + program Tác tử = Kiến trúc + Chương trình 19 Vacuum-cleaner world Ví dụ: Thế giới của máy hút bụi Percepts: location and contents, e.g., [A,Dirty] Actions: Left, Right, Suck, NoOp Các nhận thức: Ví trí và mức độ sạch sẽ Ví dụ: [A, Bẩn], [B, Bẩn] Các hành động: Di chuyển (máy hút bụi) sang trái, sang phải, hút bụi, hoặc không làm gì 20 A vacuum-cleaner agent Tác tử máy hút bụi function Reflex-Vacuum-Agent( [location, status]) returns an action if status = Dirty then return Suck else if location = A then return Right else if location = B then return Left 21 Rational Agents Tác tử hợp lý Tác tử làm đúng việc được coi là hợp lý A rational agent is one that does the right thing 22 Rational agents Tác tử hợp lý An agent should strive to "do the right thing", based on what it can perceive and the actions it can perform. The right action is the one that will cause the agent to be most successful Performance measure: An objective criterion for success of an agent's behavior E.g., performance measure of a vacuum-cleaner agent could be amount of dirt cleaned up, amount of time taken, amount of electricity consumed, amount of noise generated, etc. Tác tử cần phấn đấu để “làm đúng việ cần làm”, dựa trên những gì nó nhận thức (nhận biết) được và dựa trên các hành động mà nó có thể thực hiện Một hành động đúng (hợp lý) là hành động giúp cho tác tử đạt được thành công cao nhất đối với mục tiêu đặt ra Đánh giá hiệu quả hoạt động: là tiêu chuẩn để đánh giá mức độ thành công trong hoạt động của một tác tử Ví dụ: Tiêu chí đánh giá hiệu quả hoạ động của một tác tử máy hút bụi có th là: mức độ làm sạch, thời gian hút bụi, mức độ điện năng tiêu tốn, mức độ tiếng ồn gây ra, 23 Rational agents Tác tử hợp lý Rational Agent: For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has. Tác tử hợp lý Với mỗi chuỗi nhận thức có được, Một tác tử hợp lý cần phải lựa chọn một hành động giúp cực đại hóa tiêu chí đánh giá hiệu quả hoạt động của tác tử đó, Dựa trên các thông tin được cung cấp bởi chuỗi nhận thức và các tri thức được sở hữu bởi tác tử đó 24 Rational agents Tác tử hợp lý Rationality is distinct from omniscience (all-knowing with infinite knowledge) Agents can perform actions in order to modify future percepts so as to obtain useful information (information gathering, exploration) An agent is autonomous if its behavior is determined by its own experience (with ability to learn and adapt) Sự hợp lý ≠ Sự thông suốt mọi thứ Sự thông mọi thứ = Biết tất cả mọi thứ, với tri thức vô hạn Vì các nhận thức có thể không cung cấp tất cả các thông tin liên quan Các tác tử có thể thực hiện các hành động nhằm thay đổi các nhận thức trong tương lai, với mục đích thu được các thông tin hữu ích (ví dụ: thu thập thông tin, khám phá tri thức) Tác tử tự trị là một tác tử mà các hành động của nó được quyết định bởi chính kinh nghiệm của tác tử đó (cùng với khả năng học và thích nghi) 25 Autonomy in Agents Sự độc lập của tác tử Tác tử hành động theo kinh nghiệm riêng của nó thì tác tử là độc lập. The autonomy of an agent is the extent to which its behaviour is determined by its own experience 26 PEAS - Môi trường công việc PEAS: Performance measure, Environment, Actuators, Sensors Must first specify the setting for intelligent agent design Consider, e.g., the task of designing an automated taxi driver: – Performance measure – Environment – Actuators – Sensors PEAS: – Performance measure: Tiêu chí đánh giá hiệu quả hoạt động, – Environment: Môi trường xung quanh, – Actuators: Các bộ phận hành động, – Sensors: Các bộ phận cảm biến Để thiết kế một tác tử thông minh, trước tiên cần phải xác định các giá trị của các thành phần của PEAS 27 PEAS - Môi trường công việc Must first specify the setting for intelligent agent design Consider, e.g., the task of designing an automated taxi driver: – Performance measure: Safe, fast, legal, comfortable trip, maximize profits – Environment: Roads, other traffic, pedestrians, customers – Actuators: Steering wheel, accelerator, brake, signal, horn – Sensors: Cameras, sonar, speedometer, GPS, odometer, engine sensors, keyboard Để thiết kế một tác tử thông minh, trước tiên cần phải xác định các giá trị của các thành phần của PEAS Ví dụ: Thiết kế một tác tử lái xe taxi tự động – Đánh giá hiệu quả hoạt động (P): an toàn, nhanh, đúng luật giao thông, mức độ hài lòng của khách hàng, tối ưu lợi nhuận, – Môi trường xung quanh (E): các con đường (phố), các phương tiện khác cùng tham gia giao thông, những người đi bộ, các khách hàng, – Các bộ phận hành động (A): bánh lái, chân ga, phanh, đèn tín hiệu, còi xe, – Các bộ phận cảm biến (S): máy quay (cameras), đồng hồ tốc độ, GPS, đồng hồ đo khoảng cách quãng đường, các bộ cảm biến động cơ, 28 PEAS - Môi trường công việc Agent: Medical diagnosis system Performance measure: Healthy patient, minimize costs, lawsuits Environment: Patient, hospital, staff Actuators: Screen display (questions, tests, diagnoses, treatments, referrals) Sensors: Keyboard (entry of symptoms, findings, patient's answers) Ví dụ: Thiết kế một tác tử chuẩn đoán y tế Đánh hiệu quả hoạt động (P): mức độ sức khỏe của bệnh nhân, cực tiểu hóa các chi phí, các việc kiện cáo Môi trường xung quanh (E): bệnh nhân, bệnh viện, nhân viên y tế Các bộ phận hành động (A): hiển thị trên màn hình các câu hỏi, các xét nghiệm, các chuẩn đoán, các điều trị, các chỉ dẫn Các bộ phận cảm biến (S): bàn phím để nhập vào các thông tin về triệu chứng, các trả lời của bệnh nhân đối với các câu hỏi 29 PEAS - Môi trường công việc Agent: Part-picking robot Performance measure: Percentage of parts in correct bins Environment: Conveyor belt with parts, bins Actuators: Jointed arm and hand Sensors: Camera, joint angle sensors Ví dụ: Thiết kế một tác tử nhặt đồ vật Đánh giá hiệu quả hoạt động (P): tỷ lệ (bao nhiêu phần trăm) các đồ vật được đặt vào đúng các thùng Môi trường xung quanh (E): dây chuyền chuyển động trên đó có các đồ vật, các thùng đựng Các bộ phận hành động (A): cánh tay và bàn tay được kết nối Các bộ phận cảm biến (S): máy quay (camera), các bộ cảm biến các góc độ (các hướng) 30 PEAS - Môi trường công việc Agent: Interactive English tutor Performance measure: Maximize student's score on test Environment: Set of students Actuators: Screen display (exercises, suggestions, corrections) Sensors: Keyboard Ví dụ: Thiết kế một tác tử dạy tiếng Anh tương tác Đánh giá hiệu quả hoạt động (P): cực đại hóa điểm thi tiếng Anh của học viên Môi trường xung quanh (E): một nhóm học viên Các bộ phận hành động (A): hiển thị màn hình các bài tập, các gợi ý, sửa (chữa) bài tập Các bộ phận cảm biến (S): bàn phím 31 Environment types Các kiểu môi trường Fully observable (vs. partially observable): An agent's sensors give it access to the complete state of the environment at each point in time. Deterministic (vs. stochastic): The next state of the environment is completely determined by the current state and the action executed by the agent. (If the environment is deterministic except for the actions of other agents, then the environment is strategic) Episodic (vs. sequential): The agent's experience is divided into atomic "episodes" (each episode consists of the agent perceiving and then performing a single action), and the choice of action in each episode depends only on the episode itself. Có thể quan sát được hoàn toàn ( quan sát được một phần): Các bộ cảm biến của một tác tử cho phép nó truy cập tới trạng thái đầy đủ của môi trường tại mỗi thời điểm Xác định ( ngẫu nhiên): Trạng thái tiếp theo của môi trường được xác định hoàn toàn dựa trên trạng thái hiện tại và hành động của tác tử (tại trạng thái hiện tại này). Nếu một môi trường là xác định, ngoại trừ đối với các hành động của các tác tử khác, thì gọi là môi trường chiến lược Phân đoạn ( liên tiếp): Lịch sử kinh nghiệm của tác tử được chia thành các giai đoạn. Mỗi giai đoạn bao gồm việc nhận thức của tác tử và hành động mà nó thực hiện. Ở mỗi giai đoạn, việc lựa chọn hành động để thực hiện chỉ phụ thuộc vào giai đoạn đó (không phụ thuộc vào các giai đoạn khác) 32 Environment types Các kiểu môi trường Static (vs. dynamic): The environment is unchanged while an agent is deliberating. (The environment is semidynamic if the environment itself does not change with the passage of time but the agent's performance score does) Discrete (vs. continuous): A limited number of distinct, clearly defined percepts and actions. Single agent (vs. multiagent): An agent operating by itself in an environment. Tĩnh ( động): Môi trường không thay đổi trong khi tác tử cân nhắc (xem nên đưa ra hành động nào). Môi trường bán động (semi- dynamic) là môi trường mà khi thời gian trôi qua thì nó (môi trường) không thay đổi, nhưng hiệu quả hoạt động của tác tử thì thay đổi. Ví dụ: Các chương trình trò chơi có tính giờ Rời rạc ( liên tục): Tập các nhận thức và các hành động là hữu hạn, được định nghĩa phân biệt rõ ràng Tác tử đơn lẻ ( đa tác tử): Một tác tử hoạt động độc lập (không phụ thuộc / liên hệ với các tác tử khác) trong một môi trường 33 Environment types Các kiểu môi trường Chess with Chess without Taxi driving a clock a clock Fully observable Yes Yes No Deterministic Strategic Strategic No Episodic No No No Static Semi Yes No Discrete Yes Yes No Single agent No No No The environment type largely determines the agent design The real world is (of course) partially observable, stochastic, sequential, dynamic, continuous, multi-agent Kiểu của môi trường có ảnh hưởng quyết định đối vớiviệc thiết kế tác tử Môi trường trong thực tế thường có các đặc điểm: chỉ có thể quan sát được một phần, ngẫu nhiêu, liên tiếp, thay đổi, liên tục, đa tác tử 34 Agent functions and programs An agent is completely specified by the agent function mapping percept sequences to actions One agent function (or a small equivalence class) is rational Aim: find a way to implement the rational agent function concisely 35 Table-lookup agent Drawbacks: – Huge table – Take a long time to build the table – No autonomy – Even with learning, need a long time to learn the table entries 36 Agent types Các kiểu tác tử Four basic types in order of increasing generality: Simple reflex agents Model-based reflex agents Goal-based agents Utility-based agents 4 kiểu tác tử cơ bản Tác tử phản xạ đơn giản Tác tử phản xạ dựa trên mô hình Tác tử dựa trên mục tiêu Tác tử dựa trên lợi ích 37 Simple reflex agents Tác tử phản xạ đơn giản 38 Simple reflex agents Tác tử phản xạ đơn giản