Video
Đăng bởi Ban biên tập OpenER ·
Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
[AUDIO OUT] PIETER ABBEEL: Hi.
[MẤT ÂM THANH] PIETER ABBEEL: Xin chào.
Hi. Welcome, everyone. This is the second lecture for 188. Let's start with a couple of announcements.
Xin chào. Chào mừng các bạn. Đây là bài giảng thứ hai của môn 188. Ta bắt đầu với vài thông báo.
The first one, Project Zero, Python tutorial was due yesterday. OK. If you didn't do it, it's not a disaster because it's zero points on it.
Thứ nhất, Project Zero, phần hướng dẫn Python, đã hết hạn hôm qua. Được rồi. Nếu bạn chưa làm thì cũng không phải thảm họa vì bài này không có điểm.
But it's our way to check that you're in the class. So if you didn't do it, we might be worried that you're not in the class. So please do it.
Nhưng đây là cách để chúng tôi kiểm tra bạn có theo lớp hay không. Nếu bạn chưa làm, chúng tôi có thể lo rằng bạn không còn học lớp này. Vì vậy hãy làm nhé.
It's also a good way to get to know our submission system.
Đây cũng là dịp tốt để làm quen với hệ thống nộp bài.
There is also a homework zero. It's a math self-diagnostic. Motivation is that the first three to five weeks will be pretty light on math. And then things will change.
Ngoài ra còn có homework zero. Đó là bài tự đánh giá về toán. Lý do là từ ba đến năm tuần đầu sẽ khá nhẹ về toán. Rồi mọi thứ sẽ thay đổi.
And when things will change, it will be too late for you to drop the class.
Và khi đó thì đã quá muộn để bạn rút khỏi lớp.
And so we want you to be able to know ahead of time what you're getting yourself into and analyze your math skills now while you can still drop, rather than after it's too late.
Vì vậy chúng tôi muốn bạn biết trước mình sắp đối mặt với điều gì và đánh giá khả năng toán ngay bây giờ khi vẫn còn có thể rút, thay vì khi đã quá muộn.
Homework one search will go out this week. There will be two components — electronic and written. We'll have an announcement about it later tonight. Typically, homeworks are due on Mondays.
Homework một về tìm kiếm sẽ được đăng trong tuần này. Bài có hai phần: phần điện tử và phần viết. Tối nay chúng tôi sẽ có thông báo về bài này. Thông thường, homework hết hạn vào thứ Hai.
So kind of get used to that in some sense, but there's an exception next week. Because it's Labor Day on Monday, the homework is going to be due on Tuesday exceptionally.
Các bạn nên quen với điều đó, nhưng tuần sau có ngoại lệ. Vì thứ Hai là ngày Lễ Lao động, homework sẽ ngoại lệ hết hạn vào thứ Ba.
But keep in mind that generally homeworks are going to be due on Mondays. This is just an exception because of Labor Day.
Nhưng hãy nhớ rằng nói chung homework hết hạn vào thứ Hai. Đây chỉ là ngoại lệ do Lễ Lao động.
Project one is also going out this week and will be due sometime next week, Friday afternoon. It's longer than most projects.
Project một cũng được đăng trong tuần này và hết hạn vào chiều thứ Sáu tuần sau. Bài này dài hơn hầu hết các project khác.
And it's the best way for you to test if programming-wise you are prepared for this class. If your programming goes OK for project one, you should be good for all the future projects.
Đây là cách tốt nhất để bạn kiểm tra xem về lập trình mình đã sẵn sàng cho lớp này chưa. Nếu bạn làm project một ổn, bạn sẽ ổn với mọi project sau này.
Project zero is not a good way to check if you are prepared for this class. It's just a way to check if you have a Python installed and can submit into the system.
Project zero không phải cách tốt để kiểm tra bạn đã sẵn sàng cho lớp này chưa. Nó chỉ kiểm tra xem bạn đã cài Python chưa và có nộp được bài vào hệ thống không.
Sections start this week. The first one is happening, I think, today at 4:00 PM. There was a bunch of them today, tomorrow, and then Thursday. You can go to a any section you'd like.
Các buổi section bắt đầu từ tuần này. Buổi đầu tiên diễn ra hôm nay lúc 4 giờ chiều, tôi nghĩ vậy. Có nhiều buổi vào hôm nay, ngày mai và thứ Năm. Bạn có thể dự bất kỳ section nào.
But you'll have priority in the one that you signed up for on Piazza.
Nhưng bạn sẽ được ưu tiên ở buổi mà bạn đã đăng ký trên Piazza.
So just in case there's too many people in one room that you don't fit, the people who signed up for that time slot have priority, if you're one of the first 35 to sign up.
Phòng hợp có quá đông người không đủ chỗ thì những người đăng ký khung giờ đó sẽ được ưu tiên, nếu bạn nằm trong 35 người đăng ký đầu tiên.
Instructional accounts. There are instructions in a Piazza post, our welcome post, that say you need to go find those accounts online. Also, that you don't need them, but some of you really want them.
Về tài khoản instructional. Có hướng dẫn trong bài đăng chào mừng trên Piazza, bảo bạn cách tìm các tài khoản đó trên mạng. Bạn không cần chúng, nhưng một số bạn rất muốn có.
And if you really want them, there's instructions online. There are some pinned posts on Piazza. Those are the ones you maximally want to pay attention to.
Nếu bạn thật sự muốn, hướng dẫn có trên mạng. Có một số bài ghim trên Piazza. Đó là những bài bạn nên đặc biệt chú ý.
Those are our announcements that are currently relevant or relevant throughout the semester. So keep that in mind. And then the most frequently asked question is can you add me to B courses?
Đó là các thông báo hiện đang liên quan hoặc liên quan suốt học kỳ. Hãy nhớ điều đó. Câu hỏi được hỏi nhiều nhất là: thầy có thể thêm em vào B courses không?
But we don't use B courses for 188. So none of you will be added to B courses. Nobody is on it. Nobody will be on it.
Nhưng chúng tôi không dùng B courses cho 188. Nên không ai được thêm vào B courses cả. Không ai ở trên đó. Cũng sẽ không ai ở trên đó.
We do use other things, so make sure you know there is a website. There is Piazza and Gradescope. Any questions about logistics? Yes?
Chúng tôi dùng những thứ khác, nên hãy chắc là bạn biết có một trang web. Có Piazza và Gradescope. Có câu hỏi nào về hậu cần không? Bạn nào?
STUDENT
[INAUDIBLE] PIETER ABBEEL: Yeah, so homework one will officially release later today. And there will be a post on Piazza that links to all the relevant things for you to work on.
[KHÔNG NGHE RÕ] PIETER ABBEEL: Vâng, homework một sẽ chính thức được đăng hôm nay. Sẽ có một bài trên Piazza chứa liên kết đến mọi thứ bạn cần để làm bài.
So just a little bit more patience for that.
Các bạn kiên nhẫn thêm một chút nhé.
Any the other logistical questions? Another frequently asked question is, how about AI research? Wouldn't it be cool to do AI research? And I agree.
Còn câu hỏi hậu cần nào khác không? Một câu hỏi thường gặp khác là, còn nghiên cứu AI thì sao? Làm nghiên cứu AI chẳng phải rất thú vị sao? Tôi đồng ý.
I mean, that's half of my job is doing AI research. The other half is AI teaching. So obviously, I'm with you. AI research is good to do, a lot of fun.
Một nửa công việc của tôi là làm nghiên cứu AI. Nửa còn lại là giảng dạy AI. Nên rõ ràng là tôi đứng về phía các bạn. Nghiên cứu AI rất đáng làm và rất vui.
The way research tends to work is every professor effectively runs their own lab and has their own methodology on how and when to get new students involved.
Nghiên cứu thường vận hành thế này: mỗi giáo sư về cơ bản điều hành phòng thí nghiệm riêng, với cách riêng về việc khi nào và làm sao đưa sinh viên mới vào.
So if you're interested in AI research, check out the bair.berkeley.edu site. Check out the professors listed there.
Nếu bạn quan tâm đến nghiên cứu AI, hãy xem trang bair.berkeley.edu. Xem các giáo sư được liệt kê ở đó.
And then check their pages, see what they work on, see who might be good fits, and then individually contact them. Some of them don't read email, then your email will not be read.
Rồi xem trang của họ, họ làm gì, ai có thể hợp với bạn, rồi liên hệ riêng từng người. Một số người không đọc email, vậy thì email của bạn sẽ không được đọc.
But they might still have office hours, or they might be possibly other ways to catch in person. Every professor has their own way of communicating or not communicating.
Nhưng họ vẫn có thể có giờ tiếp sinh viên, hoặc có thể có những cách khác để gặp trực tiếp. Mỗi giáo sư có cách liên lạc riêng, hoặc không liên lạc gì cả.
It varies. But that would be your best starting point. And there is no unified entry into this. It's all on a per professor basis.
Mỗi người một khác. Nhưng đó sẽ là điểm khởi đầu tốt nhất. Và không có một cổng vào chung cho việc này. Tất cả đều tùy từng giáo sư.
Question here.
Câu hỏi ở đây.
STUDENT
[INAUDIBLE] PIETER ABBEEL: Oh, the asterisks next to the names refers to professors who are kind of at their core working on AI.
[KHÔNG NGHE RÕ] PIETER ABBEEL: À, dấu sao cạnh tên chỉ các giáo sư mà về cốt lõi làm việc về AI.
That's kind of like the main thing they work on. Whereas, the ones without asterisks often work on very closely related topics, but they might not call themselves necessarily AI faculty.
Đó gần như là lĩnh vực chính mà họ làm. Còn những người không có dấu sao thường làm các chủ đề liên quan rất gần, nhưng họ có thể không nhất thiết tự gọi mình là giảng viên AI.
But they work on things that in practice are extremely close.
Nhưng thực tế những gì họ làm cực kỳ gần với AI.
In my particular case, the way I tend to recruit students is through email. So just email me your transcript, your resume, and I'll look at that and see from there.
Với tôi, cách tôi thường tuyển sinh viên là qua email. Các em cứ gửi email cho tôi bảng điểm và CV, tôi sẽ xem rồi tính tiếp.
I got to warn you, I get like more than 100 per semester. And I can only get three or four or five involved in a semester. But you should try.
Tôi phải báo trước, mỗi học kỳ tôi nhận hơn 100 email. Mà mỗi học kỳ tôi chỉ nhận được ba, bốn hoặc năm bạn. Nhưng các em cứ thử.
And the same with other faculty, you should try if you're interested in research, and then see where you might be able to get involved. Any questions about that?
Với các giảng viên khác cũng vậy, nếu các em quan tâm đến nghiên cứu thì cứ thử, rồi xem mình có thể tham gia ở đâu. Có câu hỏi nào về phần này không?
OK. Let's get started on the technical topics then. Today's topic is search. What does that mean?
Được rồi. Vậy ta bắt đầu vào các chủ đề kỹ thuật. Chủ đề hôm nay là tìm kiếm. Điều đó nghĩa là gì?
We're going to discuss agents that plan ahead, rather than just react to a current situation. We'll formalize this into search problems.
Ta sẽ bàn về các tác tử biết lập kế hoạch trước, thay vì chỉ phản ứng với tình huống hiện tại. Ta sẽ hình thức hóa thành các bài toán tìm kiếm.
And this is going to be a recurring theme throughout the course, is that we will look at some high level intuition, some notion of the type of problem we're interested in.
Và đây sẽ là một mô-típ lặp lại xuyên suốt môn học: ta sẽ bắt đầu từ trực giác ở mức cao, một khái niệm về loại bài toán mình quan tâm.
We'll then show a formalization. For example, search problem is a formalization of real world settings into something mathematically workable.
Sau đó ta sẽ hình thức hóa nó. Ví dụ, bài toán tìm kiếm là một sự hình thức hóa các tình huống thực tế thành một thứ có thể xử lý bằng toán học.
And then we'll have algorithms that can work with that mathematical interface to solve the problem.
Và rồi ta có các thuật toán làm việc với giao diện toán học đó để giải bài toán.
And the algorithms we'll see today are depth first, breadth first, a uniform cost search, and we'll expand on that in the next lecture. So agents that plan.
Các thuật toán hôm nay ta sẽ thấy là tìm kiếm theo chiều sâu, theo chiều rộng, và tìm kiếm chi phí đều, và ta sẽ mở rộng phần này ở bài sau. Vậy, các tác tử biết lập kế hoạch.
Before we dive into agents that plan, let's maybe contrast it by a more naive type of agent, the reflex agent because that might be the simplest way to just write up some AI agent.
Trước khi đi sâu vào các tác tử lập kế hoạch, hãy đối chiếu với một loại tác tử đơn giản hơn, tác tử phản xạ, vì có lẽ đó là cách đơn giản nhất để viết ra một tác tử AI.
So what are reflex agents? Reflex agents are agents that have a current precept, maybe some memory.
Vậy tác tử phản xạ là gì? Tác tử phản xạ là tác tử có tri giác hiện tại, có thể có một ít bộ nhớ.
And based on that, make a decision, but without consideration of the consequences of their actions. So let's see. Who here is maybe like sometimes a reflex agent?
Dựa vào đó nó ra quyết định, nhưng không xét đến hệ quả của hành động. Nào, thử xem. Ai ở đây đôi khi là một tác tử phản xạ?
Who thinks they're sometimes a reflex agent? OK. Why?
Ai nghĩ mình đôi khi là tác tử phản xạ? Được. Tại sao?
STUDENT
[INAUDIBLE] PIETER ABBEEL: So the answer was because sometimes just instinctively you feel what to do, and you just do it. You don't reason through all the consequences.
[KHÔNG NGHE RÕ] PIETER ABBEEL: Câu trả lời là đôi khi theo bản năng ta cảm thấy phải làm gì và làm luôn. Ta không suy xét hết mọi hệ quả.
Sometimes good consequences result, sometimes bad, I guess. But a good example would be something where maybe an insect, a fly is flying to your face.
Đôi khi kết quả tốt, đôi khi xấu. Một ví dụ hay là khi một con côn trùng, con ruồi bay vào mặt bạn.
And you don't want to go, OK, well, if I keep my eyes open, what will happen? If I close them, what will happen?
Bạn không muốn nghĩ: nếu mình mở mắt thì chuyện gì sẽ xảy ra? Nếu nhắm mắt thì sao?
You just want to close your eyes and be done with it. That would be a reflex compared to planning, which is thinking through all the consequences.
Bạn chỉ muốn nhắm mắt lại cho xong. Đó là phản xạ, so với lập kế hoạch là suy nghĩ qua mọi hệ quả.
So reflexes make a lot of sense, especially when you need to react quickly. Can reflex agents be rational?
Phản xạ rất hợp lý, nhất là khi ta cần phản ứng nhanh. Tác tử phản xạ có thể hợp lý (rational) không?
Meaning, a rational agent is an agent that optimizes expected utility.
Nghĩa là, tác tử hợp lý là tác tử tối ưu hóa độ hữu dụng kỳ vọng.
I hear a yes. Why yes? Anybody?
Tôi nghe có tiếng "có". Tại sao có? Ai trả lời không?
STUDENT
[INAUDIBLE] PIETER ABBEEL: So the answer is by reacting quickly you might be doing the right thing.
[KHÔNG NGHE RÕ] PIETER ABBEEL: Câu trả lời là nhờ phản ứng nhanh bạn có thể làm đúng điều cần làm.
And if you're doing the right thing, indeed like your hand's in the fire, you pull it back right away instead of thinking through the consequences of will this become burned?
Và nếu làm đúng, chẳng hạn tay bạn chạm vào lửa, bạn rụt lại ngay thay vì suy xét hệ quả: liệu tay có bị bỏng không?
Will it become charcoal? What will the result be? You just pull back is much more optimal then to maybe reason through everything and might be too late.
Liệu nó có thành than không? Kết quả sẽ ra sao? Rụt tay lại ngay tối ưu hơn nhiều so với việc lý luận mọi thứ và có thể đã quá muộn.
So our definition of rational means optimal behavior. And how you reach those conclusions is decoupled from whether the agent is rational or not. And so that's a good example.
Định nghĩa hợp lý của ta nghĩa là hành vi tối ưu. Còn việc bạn đi đến kết luận bằng cách nào thì tách rời với việc tác tử có hợp lý hay không. Vậy đó là một ví dụ hay.
Let's look at a Pac-Man example. So we'll run a demo here of Pac-Man in a very simple world. And the goal is to eat all the dots as efficiently as possible.
Giờ xem một ví dụ Pac-Man. Ta sẽ chạy demo Pac-Man trong một thế giới rất đơn giản. Mục tiêu là ăn hết các chấm một cách hiệu quả nhất có thể.
And we're going to run a reflex agent, which just moves to the nearest by dot. So it looks at the nearest by dot, tries to move in that direction.
Ta chạy một tác tử phản xạ, chỉ di chuyển đến chấm gần nhất. Nó nhìn chấm gần nhất rồi cố đi theo hướng đó.
Here's what happens. There's nothing better available for you to do. So doing something as simple as move in the direction of the closest dot does succeed. Now, let's look at another case.
Đây là kết quả. Không có cách nào tốt hơn để làm. Vậy một việc đơn giản như đi về phía chấm gần nhất vẫn thành công. Giờ xem một trường hợp khác.
Same piece of code. Look at the nearest by dot and try to move in that direction. So initially, it's going to go north, a lot of west, some more north.
Cùng đoạn mã đó. Nhìn chấm gần nhất và cố đi theo hướng đó. Ban đầu nó đi lên bắc, nhiều về tây, rồi thêm bắc nữa.
And it's east, east, east, east, east, east, east, east, east, and nothing happens.
Và nó đi đông, đông, đông, đông, đông, đông, đông, đông, đông, mà chẳng có gì xảy ra.
Because by moving east, it bumps into the wall, encounters the same situation, has the same reflex, repeats over and over and over. And actually, it loses points here.
Vì đi về phía đông thì nó đâm vào tường, gặp lại đúng tình huống đó, có cùng phản xạ, và cứ lặp đi lặp lại mãi. Thực ra nó còn bị mất điểm.
So in the one idiot Pac-Man world, when you waste time or every step that passes you lose a point to encourage you to be more efficient at completing the game.
Trong thế giới Pac-Man đơn giản này, mỗi bước trôi qua hay lãng phí thời gian là bị trừ một điểm, để khuyến khích bạn hoàn thành trò chơi hiệu quả hơn.
So this is a reflex agent that's clearly not optimal. We'd really would want it to go around that wall and get the dot, but it's not going to do that.
Đây rõ ràng là tác tử phản xạ không tối ưu. Ta thực sự muốn nó đi vòng qua bức tường đó và lấy chấm, nhưng nó sẽ không làm vậy.
So we've seen a reflex agent that is rational, one that's not rational. Oh, quick note here. In the slides that you'll find online, the PowerPoint version has the videos of the demos embedded.
Vậy ta đã thấy một tác tử phản xạ hợp lý, và một tác tử không hợp lý. À, lưu ý nhanh một chút. Trong các slide bạn sẽ tìm thấy trên mạng, bản PowerPoint có nhúng sẵn video của các demo.
So if at home, you're kind of reworking through the slides, and you're like, oh, what happened again in lecture one, this demo was run, you can click Play.
Nên nếu ở nhà bạn xem lại các slide, và tự hỏi: ở bài giảng một đã xảy ra gì nhỉ, demo này được chạy ra sao, bạn có thể bấm Play.
And then you can watch the same demo at home as a video rather than a live demo. OK. So we've seen reflex agents. How about planning agents?
Và bạn có thể xem lại đúng demo đó ở nhà dưới dạng video thay vì demo trực tiếp. Được rồi. Vậy là ta đã thấy các tác tử phản xạ. Còn các tác tử lập kế hoạch thì sao?
Planning agents ask themselves the question, what if? So they hypothesize if they were to take a sequence of actions, what would the result be?
Tác tử lập kế hoạch tự đặt câu hỏi: nếu như thì sao? Tức là nó giả định nếu thực hiện một chuỗi hành động, thì kết quả sẽ ra sao?
A requirement for this is that the agent has a model of how the world works.
Yêu cầu cho việc này là tác tử phải có một mô hình về cách thế giới vận hành.
If you don't have a model of how the world works, you cannot reason through the possible consequences of your actions. You also have to have some kind of goal.
Nếu bạn không có mô hình về cách thế giới vận hành, bạn không thể suy luận về các hệ quả có thể xảy ra của các hành động của mình. Bạn cũng cần có một dạng mục tiêu nào đó.
Because the planning agent would have a sequence of actions its hypothesizing about, and then evaluating them based on whether they achieved the goal or not.
Vì tác tử lập kế hoạch sẽ có một chuỗi hành động mà nó đang giả định, rồi đánh giá chúng dựa trên việc chúng có đạt được mục tiêu hay không.
The goal could sometimes be a single thing that needs to be achieved, or it could be a test, a condition that needs to be met that can be met in many ways.
Mục tiêu đôi khi là một thứ duy nhất cần đạt được, hoặc có thể là một phép kiểm tra, một điều kiện cần thỏa mãn mà có thể thỏa mãn bằng nhiều cách.
And you just need to meet the condition in some way. There are questions you will be able to ask and hopefully answer about planning algorithms when we see them.
Và bạn chỉ cần thỏa mãn điều kiện đó bằng cách nào đó. Có những câu hỏi bạn sẽ có thể đặt ra và hy vọng trả lời được về các thuật toán lập kế hoạch khi ta học chúng.
An algorithm could be optimal or suboptimal. Optimal means that you achieve goals in minimum cost.
Một thuật toán có thể tối ưu hoặc không tối ưu. Tối ưu nghĩa là bạn đạt mục tiêu với chi phí tối thiểu.
Complete means that when there exists a solution, you find it. And then we'll look at some planning versus re-planning in the next demo here.
Đầy đủ (complete) nghĩa là khi tồn tại lời giải, bạn tìm ra nó. Và ta sẽ xem lập kế hoạch so với lập kế hoạch lại trong demo tiếp theo.
So we'll start with a showcase of a mastermind agent that is planning through everything.
Ta bắt đầu với một tác tử thiên tài lập kế hoạch cho mọi thứ.
So same maze again as we just saw. Now, it's going to be a planning agent. When I hit Start, we're going to see some planning happening down here.
Vẫn là mê cung như ta vừa thấy. Lần này nó sẽ là tác tử lập kế hoạch. Khi tôi bấm Start, ta sẽ thấy việc lập kế hoạch diễn ra ở dưới này.
Let's see. It's actually pre-calculating to be ready for planning. It's done that. It's done 1,000 expansions, 2,000 expansions.
Để xem nào. Nó đang tính trước để sẵn sàng lập kế hoạch. Xong rồi. Nó đã mở rộng 1.000 lần, 2.000 lần.
This is reasoning through many possible consequences of actions. It's then found what it knows is the optimal sequence of actions to clear this board. And then executes that sequence of actions.
Nó đang suy luận qua nhiều hệ quả có thể xảy ra của các hành động. Rồi nó tìm ra chuỗi hành động mà nó biết là tối ưu để dọn sạch bàn chơi này. Và sau đó thực thi chuỗi hành động đó.
Now, the reason it took a while for this vision to get going is because a lot of sequence of actions to consider.
Lý do nó mất một lúc mới bắt đầu chạy là vì có rất nhiều chuỗi hành động phải xét.
And before you can ensure that you've found the optimal one, you have to consider quite a few in this scenario. Sometimes it's not practical to wait this long.
Và trước khi chắc chắn đã tìm ra chuỗi tối ưu, bạn phải xét khá nhiều chuỗi trong tình huống này. Đôi khi chờ lâu như vậy là không thực tế.
And you might want to do something slightly different, which you'll do in some of your project ones also, which is re-planning.
Và bạn có thể muốn làm khác đi một chút, điều mà bạn cũng sẽ làm trong một số project, đó là lập kế hoạch lại.
So what we're going to watch here is an agent that doesn't plan an entire sequence ahead of time, but it just plans to the nearest dot. So it checks where is the nearest dot?
Vậy điều ta sắp xem ở đây là một tác tử không lập cả chuỗi hành động từ trước, mà chỉ lập kế hoạch đến chấm gần nhất. Nó kiểm tra chấm gần nhất ở đâu?
What's my path to get there? Executes that plan.
Đường đi đến đó là gì? Thực thi kế hoạch đó.
After it's executed that plan, formulates a new planning problem where it will plan path to the next nearest dot and repeats over and over and over.
Sau khi thực thi xong, nó lập một bài toán lập kế hoạch mới để tìm đường đến chấm gần nhất kế tiếp và lặp đi lặp lại như vậy.
So this one can start acting almost right away and is continuously re-planning throughout execution to find the shortest path to the next dot.
Nên tác tử này có thể hành động gần như ngay lập tức và liên tục lập kế hoạch lại trong suốt quá trình thực thi để tìm đường ngắn nhất đến chấm kế tiếp.
OK. So we've seen a few examples here. And it's now started formalizing what it means to be a search problem. What are the key components?
Được rồi. Vậy ta đã thấy vài ví dụ. Và giờ ta bắt đầu hình thức hóa thế nào là một bài toán tìm kiếm. Các thành phần chính là gì?
A state space. So whenever you are formulating a problem in the real world that you try to solve, a state space will be something you have to formulate for it.
Một không gian trạng thái. Khi bạn mô hình hóa một bài toán ngoài đời thực mà bạn muốn giải, không gian trạng thái là thứ bạn phải xây dựng cho nó.
For example, for Pac-Man, the state space is a set of possible configurations of where Pac-Man is and where the dots are. Then a successor function.
Ví dụ với Pac-Man, không gian trạng thái là tập các cấu hình có thể về vị trí của Pac-Man và vị trí của các chấm. Tiếp theo là hàm kế tiếp (successor function).
The successor function says for any given state what the actions are that are available, and what the consequence states will be.
Hàm kế tiếp cho biết với một trạng thái bất kỳ có những hành động nào khả dụng, và các trạng thái kết quả sẽ là gì.
For example, from this particular state, the agent can take either the north action or the east action. And then the results are shown on the right.
Ví dụ, từ trạng thái này, tác tử có thể thực hiện hành động đi lên phía bắc hoặc đi sang phía đông. Và các kết quả được hiển thị bên phải.
So the successor function encodes how the world works.
Vậy hàm kế tiếp mã hóa cách thế giới vận hành.
They need a start state and a goal test. Start state could be wherever you are currently in. And the goal test would be the condition that you want your agent to meet.
Cần có một trạng thái bắt đầu và một phép kiểm tra đích. Trạng thái bắt đầu có thể là nơi bạn đang đứng hiện tại. Còn phép kiểm tra đích là điều kiện mà bạn muốn tác tử thỏa mãn.
The solution to your problem would be a sequence of actions, which we'll call a plan, which transformed the start state into a state that satisfies the goal condition.
Lời giải cho bài toán của bạn sẽ là một chuỗi hành động, mà ta sẽ gọi là một kế hoạch, biến trạng thái bắt đầu thành một trạng thái thỏa mãn điều kiện đích.
Now, the beauty of having this kind of interface up here is that once we agree to an interface like this, any real world problem we can cast this way, if we then have an algorithm that can work with this interface, that algorithm can solve that real world problem.
Cái hay của việc có giao diện như thế này là một khi ta thống nhất một giao diện như vậy, bất kỳ bài toán thực tế nào ta cũng có thể biểu diễn theo cách này, và nếu có một thuật toán làm việc được với giao diện này, thuật toán đó có thể giải bài toán thực tế ấy.
And so the unifying theme in this lecture and the next lecture for casting real world problems as things we'll solve with our AI algorithms is by casting them as search problems.
Và chủ đề xuyên suốt của bài giảng này và bài sau để đưa các bài toán thực tế thành thứ mà ta giải bằng các thuật toán AI là biểu diễn chúng thành các bài toán tìm kiếm.
OK. Search problems are always just models.
Được rồi. Bài toán tìm kiếm luôn chỉ là các mô hình.
And so a lot of the art will be in thinking through what it means to be a good model of the problem that you're trying to solve in the real world.
Vì vậy phần lớn nghệ thuật nằm ở việc suy nghĩ xem thế nào là một mô hình tốt cho bài toán mà bạn đang cố giải ngoài đời thực.
So let's look at an example. Let's say you want to find a path. And this is a map — well, a simplified map — of Romania.
Hãy xem một ví dụ. Giả sử bạn muốn tìm một đường đi. Và đây là bản đồ, à, một bản đồ đơn giản hóa, của Romania.
And maybe you want to start in [INAUDIBLE],, which would be your start state, and end up in Bucharest, where you have the airport.
Và có thể bạn muốn bắt đầu ở [KHÔNG NGHE RÕ], đó sẽ là trạng thái bắt đầu, và kết thúc ở Bucharest, nơi có sân bay.
To model this as a search problem, we need to ask the question, well, what are the states? What's the state space? Any thoughts?
Để mô hình hóa việc này thành một bài toán tìm kiếm, ta cần hỏi: các trạng thái là gì? Không gian trạng thái là gì? Các em nghĩ sao?
Yeah.
Mời em.
STUDENT
[INAUDIBLE] PIETER ABBEEL: So suggestion is, all locations. And that's indeed also the choice we made here. Since we're interested in finding paths, that seems reasonable.
[KHÔNG NGHE RÕ] PIETER ABBEEL: Gợi ý là tất cả các địa điểm. Và đó cũng chính là lựa chọn của chúng ta ở đây. Vì ta quan tâm đến việc tìm đường đi, nên cách chọn này hợp lý.
But you might go back and say, hey, the way I'm going to model this is actually different. I don't just care about the cities.
Nhưng bạn cũng có thể quay lại và nói, cách tôi mô hình hóa thực ra sẽ khác. Tôi không chỉ quan tâm đến các thành phố.
I care about more details of the path along the way. And then break it down more and so forth. But at some point, you have to make a decision.
Tôi quan tâm đến nhiều chi tiết hơn của đường đi dọc đường. Rồi chia nhỏ hơn nữa, và cứ thế. Nhưng đến một lúc nào đó, bạn phải quyết định.
And this is one reasonable decision. How about successor function? Any thoughts?
Và đây là một quyết định hợp lý. Còn hàm kế thừa thì sao? Các em nghĩ sao?
For any city, whichever cities are neighboring it, is the possible successors. So it is defined by the graph here. And the cost associated with the transition would be the distance on that edge.
Với mỗi thành phố, các thành phố lân cận nó là các trạng thái kế thừa có thể có. Nên nó được xác định bởi đồ thị ở đây. Và chi phí gắn với bước chuyển sẽ là khoảng cách trên cạnh đó.
Again, you could make other decisions in practice. You might say I don't just care about how many kilometers it is between two cities. I care about how much traffic there is.
Một lần nữa, trong thực tế bạn có thể chọn khác. Bạn có thể nói tôi không chỉ quan tâm giữa hai thành phố cách nhau bao nhiêu km. Tôi quan tâm đến mức độ giao thông.
Or I care about the number of potholes in the road. And you can adjust your cost and increase it if there's more potholes and so forth. But one choice would be distance.
Hoặc tôi quan tâm đến số ổ gà trên đường. Và bạn có thể điều chỉnh chi phí, tăng lên nếu có nhiều ổ gà hơn, v.v. Nhưng một lựa chọn là khoảng cách.
Yeah.
Mời em.
STUDENT
[INAUDIBLE] PIETER ABBEEL: So the question is, if you choose a different state space, might your successor function be different? And the answer is yes. You need to choose them in a compatible way.
[KHÔNG NGHE RÕ] PIETER ABBEEL: Câu hỏi là, nếu chọn không gian trạng thái khác, thì hàm kế thừa có khác đi không? Câu trả lời là có. Bạn cần chọn chúng sao cho tương thích với nhau.
And we'll see more examples soon where you'll see that. Indeed, once you start picking a different state space for the same type of problem, you have different successor functions.
Và sắp tới ta sẽ thấy thêm các ví dụ về điều này. Quả thật, khi bạn chọn một không gian trạng thái khác cho cùng một loại bài toán, bạn sẽ có các hàm kế thừa khác.
Start state. Well, if we need to go from [INAUDIBLE] to Bucharest, that's [INAUDIBLE]. Goal test, we need to end up in Bucharest. So is our state equal to Bucharest is our goal test.
Trạng thái bắt đầu. Nếu ta cần đi từ [KHÔNG NGHE RÕ] đến Bucharest, thì đó là [KHÔNG NGHE RÕ]. Kiểm tra đích: ta phải kết thúc ở Bucharest. Tức là trạng thái bằng Bucharest chính là phép kiểm tra đích.
What's the solution? Well, the solution would be some kind of path, maybe this path over here, or maybe you like this path.
Lời giải là gì? Lời giải sẽ là một đường đi nào đó, có thể là đường này ở đây, hoặc bạn thích đường này hơn.
We'd have to calculate maybe which one is shorter to find the optimal path. There are even longer ones. But those are possible solutions to the problem. OK.
Ta phải tính xem đường nào ngắn hơn để tìm đường đi tối ưu. Còn có những đường dài hơn nữa. Nhưng đó đều là các lời giải khả dĩ của bài toán. Được rồi.
Let's do a few more of these. Here's a Pac-Man environment. And keep in mind the world state encodes everything about the environment. So the world state would have everything about this board situation.
Ta làm thêm vài ví dụ nữa. Đây là môi trường Pac-Man. Hãy nhớ rằng trạng thái thế giới mã hóa mọi thứ về môi trường. Nên trạng thái thế giới sẽ có mọi thứ về tình huống trên bàn chơi này.
But now, the problem we're trying to solve would determine, well, we want to put in our state space for our search problem. So let's say we want to solve pathing.
Nhưng bài toán ta đang muốn giải sẽ quyết định ta đưa gì vào không gian trạng thái của bài toán tìm kiếm. Giả sử ta muốn giải bài toán tìm đường.
What would we put into our state space? Any thoughts?
Ta sẽ đưa gì vào không gian trạng thái? Các em nghĩ sao?
Location. So location makes sense because if we have location we can track where we are. And we need to go from some start to some destinations. That makes sense.
Vị trí. Vị trí hợp lý vì có vị trí thì ta theo dõi được mình đang ở đâu. Và ta cần đi từ điểm xuất phát đến đích. Vậy là hợp lý.
Successor function. Well, it'd be something about north, east, south, west, take [INAUDIBLE] certain direction. And it would have something about where the walls are. Because if you run into a wall, you don't move.
Hàm kế thừa. Nó sẽ liên quan đến bắc, đông, nam, tây, đi theo một hướng nào đó. Và nó có thông tin về vị trí các bức tường. Vì nếu đâm vào tường, bạn không di chuyển.
You stay put. So that would be encoded into the successor function.
Bạn đứng yên. Điều đó được mã hóa trong hàm kế thừa.
And the actions are part of your successor function. And then goal test would be am I at the end state I want to be at? Now, let's change it.
Và các hành động là một phần của hàm kế thừa. Còn kiểm tra đích sẽ là: tôi có đang ở trạng thái cuối mà tôi muốn đến không? Giờ ta thay đổi.
What if our goal was to eat all the dots?
Nếu mục tiêu là ăn hết các chấm thì sao?
What would our state space be now?
Không gian trạng thái bây giờ sẽ là gì?
STUDENT
[INAUDIBLE] PIETER ABBEEL: So the suggestion was food locations and the location of Pac-Man. Then we need to think about what does it mean to encode food locations?
[KHÔNG NGHE RÕ] PIETER ABBEEL: Gợi ý là vị trí thức ăn và vị trí của Pac-Man. Rồi ta cần nghĩ xem mã hóa vị trí thức ăn nghĩa là gì?
For Pac-Man, we have xy coordinates for food, different options.
Với Pac-Man, ta có tọa độ xy của thức ăn, có nhiều lựa chọn.
One possibility could be, because the map is fixed, we could say for every possible location, there was a 01 Boolean flag saying whether there is still food there or not.
Một khả năng là, vì bản đồ cố định, ta có thể nói với mỗi vị trí có thể có, có một cờ Boolean 0/1 cho biết ở đó còn thức ăn hay không.
So we'd have a long list of 01s, depending on whether there was food or not, together with the coordinates of Pac-Man. How about actions?
Vậy ta có một danh sách dài các số 0/1, tùy có thức ăn hay không, cùng với tọa độ của Pac-Man. Còn các hành động thì sao?
Action stay the same. Right? Same game — north, south, east, west. How about successor function?
Hành động vẫn như cũ. Đúng không? Vẫn thế: bắc, nam, đông, tây. Còn hàm kế thừa?
STUDENT
[INAUDIBLE] PIETER ABBEEL: So if we now need to update both the location and the binary state of the food. So that's where we have now a different successor function than before.
[KHÔNG NGHE RÕ] PIETER ABBEEL: Đúng, giờ ta cần cập nhật cả vị trí lẫn trạng thái nhị phân của thức ăn. Đó là chỗ ta có hàm kế thừa khác so với trước.
Before we are able to ignore that. Even though it might change in the real world, we just ignored it because for pathing it didn't matter. But here, we have to keep track of it.
Trước đây ta có thể bỏ qua điều đó. Dù nó có thể thay đổi trong thế giới thực, ta cứ bỏ qua vì với bài toán tìm đường thì không quan trọng. Nhưng ở đây, ta phải theo dõi nó.
And then the goal test would be whether dots have all taken on the value false.
Và kiểm tra đích sẽ là xem tất cả các chấm đã nhận giá trị false hay chưa.
And we don't need to worry about where Pac-Man is because that's not part of what we need to achieve. It's just about eating all the dots. OK.
Và ta không cần lo Pac-Man đang ở đâu vì đó không phải là một phần của điều cần đạt được. Chỉ cần ăn hết các chấm. OK.
So once we understand state spaces, the first question we can ask is, how big is our state space? So here is another maze. There's Pac-Man. There are some ghosts.
Khi đã hiểu về không gian trạng thái, câu hỏi đầu tiên ta có thể đặt ra là: không gian trạng thái lớn cỡ nào? Đây là một mê cung khác. Đây là Pac-Man. Có vài con ma.
There's 120 possible agent positions. There's a food count, 30 positions. Then 12 possible ghost positions for each ghost. And there's an agent.
Có 120 vị trí có thể cho tác tử. Số thức ăn thì có 30 vị trí. Mỗi con ma có 12 vị trí có thể. Và có một tác tử.
And the agent could be facing north, east, south, west. OK. So what's the size of the state space? Well, somehow we need to count this.
Tác tử có thể quay mặt về hướng bắc, đông, nam, tây. OK. Vậy kích thước không gian trạng thái là bao nhiêu? Ta cần đếm bằng cách nào đó.
The way you do this, you look at all the variables involved and see how many are there. So let's first look at the world state. So world state wise, how many do we have?
Cách làm là nhìn tất cả các biến liên quan và xem mỗi biến có bao nhiêu giá trị. Trước hết hãy xem trạng thái thế giới. Về trạng thái thế giới, ta có bao nhiêu?
Well, agent positions we have — not sure about this vertical bar — we have agent positions, 120 possibilities.
Vị trí tác tử thì ta có — không chắc về thanh dọc này — vị trí tác tử có 120 khả năng.
Then to know how many total states there are we need to check everything that varies and effectively multiply the count together. So food count, 30 locations that could be food or no food.
Để biết tổng số trạng thái, ta cần kiểm tra mọi thứ có thể thay đổi và nhân các số đếm lại với nhau. Thức ăn: 30 vị trí, mỗi vị trí có thể có hoặc không có thức ăn.
So that's 2 to the 30 possibilities multiplied by 120. Each ghost could be in 12 locations. So that times 12 times 12 for both ghosts.
Vậy là 2 mũ 30 khả năng, nhân với 120. Mỗi con ma có thể ở 12 vị trí. Nên nhân thêm 12 nhân 12 cho cả hai con ma.
And then the agent could be facing north, east, south, west. So the total number of world states is this product. And the thing that should make you worried here is this one over here.
Rồi tác tử có thể quay mặt về bắc, đông, nam, tây. Vậy tổng số trạng thái thế giới là tích này. Điều đáng lo ở đây là số hạng này.
We're going to have something very large in the exponent. Usually the number becomes very large. And so you have something very big to deal with. OK.
Ta có một số rất lớn nằm ở số mũ. Thường thì con số trở nên rất lớn. Và ta phải xử lý một thứ rất lớn. OK.
That's world state. How about search problem state? That depends on the type of problem we're trying to solve. Imagine we're trying to solve eat all dots.
Đó là trạng thái thế giới. Còn trạng thái của bài toán tìm kiếm thì sao? Điều đó phụ thuộc loại bài toán ta muốn giải. Giả sử ta muốn giải bài ăn hết các chấm.
OK. Well, what do we need for eating all the dots? We went through that on the previous slide. We need the agent position.
OK. Vậy để ăn hết các chấm, ta cần gì? Ta đã đi qua điều đó ở slide trước. Ta cần vị trí tác tử.
We need to know where the food is. Since the ghosts are blocked off, we don't need to know about where the ghosts are.
Ta cần biết thức ăn ở đâu. Vì các con ma bị chặn lại, ta không cần biết ma ở đâu.
And we also don't need to know about which way the agent is facing. So I end up with 120 times to 230. What if it was just pathing?
Ta cũng không cần biết tác tử đang quay mặt về hướng nào. Vậy ta có 120 nhân 2 mũ 30. Nếu chỉ là tìm đường thì sao?
Then all we need to know is the agent position. It would be 120.
Khi đó ta chỉ cần biết vị trí tác tử. Tức là 120.
And so you can start seeing here why mastermind Pac-Man who was trying to figure out the shortest path to eat all the dots had to think for a long time because actually eating all the dots means that you have a state space where you need to keep track of which dots are still present or not.
Từ đây bạn bắt đầu thấy vì sao Pac-Man mastermind, khi cố tìm đường ngắn nhất để ăn hết các chấm, phải nghĩ rất lâu, vì ăn hết các chấm nghĩa là không gian trạng thái đòi hỏi bạn phải theo dõi chấm nào còn, chấm nào không.
And this is going to be very large, especially for a bigger maze. Whereas, just pathing problem can be solved a lot more quickly. Any questions about the counts and how this works?
Và không gian này sẽ rất lớn, nhất là với mê cung lớn hơn. Trong khi đó, bài toán chỉ tìm đường có thể giải nhanh hơn nhiều. Có câu hỏi nào về cách đếm và cách nó hoạt động không?
Yes.
Vâng.
STUDENT
Do you have to account for instructions or impossible [INAUDIBLE]?
Mình có phải tính cả các chỉ dẫn hay các trường hợp bất khả thi [KHÔNG NGHE RÕ] không ạ?
PIETER ABBEEL
OK. That's a really good question. So should we account for instructions about impossible world states?
OK. Câu hỏi rất hay. Vậy ta có nên tính đến các trạng thái thế giới bất khả thi không?
For example, should we count maybe for whether ghosts can tunnel through the wall or not? Or do you have something else in mind?
Ví dụ, ta có nên tính xem ma có xuyên tường được hay không? Hay bạn đang nghĩ đến điều khác?
STUDENT
Actually, if Pac-Man [INAUDIBLE]..
Thực ra, nếu Pac-Man [KHÔNG NGHE RÕ].
PIETER ABBEEL
So I think what you're asking is, what's the exact definition of how this world works?
Tôi nghĩ bạn đang hỏi định nghĩa chính xác về cách thế giới này vận hành?
And the way it works is that once Pac-Man arrives on a position where there's a food dot, it instantly gets eaten.
Cách nó vận hành là khi Pac-Man đến một vị trí có chấm thức ăn, nó bị ăn ngay lập tức.
So there is no such notion as being on that food dot, but not yet having eaten it. The eating is automatic.
Nên không có khái niệm đang đứng trên chấm thức ăn mà chưa ăn nó. Việc ăn là tự động.
STUDENT
[INAUDIBLE] PIETER ABBEEL: Oh, I see. You're saying in the count. So that's a very good point.
[KHÔNG NGHE RÕ] PIETER ABBEEL: À, tôi hiểu rồi. Bạn nói về phép đếm. Đó là một điểm rất đúng.
When we do this count here, it's a slight overestimate of what actually could happen.
Khi đếm như thế này, ta đã ước lượng hơi dư so với những gì thực sự có thể xảy ra.
The state where Pac-Man is in a particular location and there is food there is a state that doesn't happen. And in principle, we could take it out.
Trạng thái mà Pac-Man ở một vị trí nào đó và ở đó có thức ăn là trạng thái không xảy ra. Về nguyên tắc, ta có thể loại nó ra.
And so we can actually start subtracting, in this case, a relatively small number of states from that count because they can not occur.
Vậy ta có thể trừ đi, trong trường hợp này, một số trạng thái tương đối nhỏ khỏi số đếm vì chúng không thể xảy ra.
And so what we're doing here, you're absolutely right, is essentially getting a ballpark estimate of how big this problem space is when we estimate it this way.
Và điều ta đang làm ở đây, bạn nói hoàn toàn đúng, về bản chất là ước lượng sơ bộ xem không gian bài toán lớn cỡ nào khi ước lượng theo cách này.
And we try to get it roughly right, but not up to the exact number. Yes?
Ta cố gắng ước lượng gần đúng, chứ không đến mức ra con số chính xác. Vâng?
STUDENT
What's 2 to the 30 [INAUDIBLE]??
2 mũ 30 là gì [KHÔNG NGHE RÕ]?
PIETER ABBEEL
So 2 to the 30 corresponds to the fact that for each of the 30 food locations, the dot could be present or could be absent.
2 mũ 30 tương ứng với việc ở mỗi trong 30 vị trí thức ăn, chấm có thể có mặt hoặc vắng mặt.
And so every possible combination of presence/absence is 2 to the 30.
Và mọi tổ hợp có mặt/vắng mặt có thể là 2 mũ 30.
OK. Now, let's do a little quiz.
OK. Bây giờ làm một bài đố nhỏ.
Well, let's first define the problem. The problem is defined as we want Pac-Man to eat all the dots while keeping the ghosts scared at all times.
Trước hết hãy định nghĩa bài toán. Bài toán được định nghĩa là ta muốn Pac-Man ăn hết các chấm trong khi giữ cho các con ma luôn sợ hãi.
So the way Pac-Man works is that if you eat one of those bigger dots, a power pellet, ghosts become scared for a while.
Cách Pac-Man hoạt động là nếu bạn ăn một trong những chấm lớn hơn, tức power pellet, ma sẽ sợ hãi trong một lúc.
And so what we want here is we want to find a sequence of actions and a search problem formulation corresponding that'll allow us to find that such that we'll keep the ghosts scared at all times and eat all the dots.
Vậy điều ta muốn ở đây là tìm ra một chuỗi hành động và một cách phát biểu bài toán tìm kiếm tương ứng, sao cho chúng ta tìm được lời giải mà luôn giữ cho ma sợ hãi và ăn hết các chấm.
OK. Why don't you talk to each other for a couple of minutes. And then we'll see what you come up with as the state space, successor function, and so forth.
Được rồi. Các em thảo luận với nhau vài phút nhé. Sau đó ta sẽ xem các em đề xuất không gian trạng thái, hàm kế thừa và các thành phần khác là gì.
[CHATTER] OK.
[TRÒ CHUYỆN] Được rồi.
So let's see. Let's do this by just committing in some sense grow what goes into state space. OK. Who wants to put something in the state space?
Nào, ta xem nhé. Ta cứ từng bước mở rộng dần những gì nằm trong không gian trạng thái. Được chứ? Ai muốn đưa gì vào không gian trạng thái?
Raise your hand. Any thoughts?
Giơ tay nào. Có ý kiến nào không?
STUDENT
[INAUDIBLE] PIETER ABBEEL: OK. So let's say I'll write it here. Power pellet.
[KHÔNG NGHE RÕ] PIETER ABBEEL: Được. Thầy sẽ viết ở đây. Power pellet.
STUDENT
And you can also add just the amount of time left [INAUDIBLE].
Và có thể thêm cả lượng thời gian còn lại [KHÔNG NGHE RÕ].
PIETER ABBEEL
Remaining locations.
Các vị trí còn lại.
A timer for the ghosts. OK. Anybody else wants to add something else?
Một bộ đếm thời gian cho ma. Được. Ai muốn thêm gì nữa không?
Over there.
Bạn ở đằng kia.
STUDENT
[INAUDIBLE] PIETER ABBEEL: So the regular food pellets, essentially dot Booleans, as we had before.
[KHÔNG NGHE RÕ] PIETER ABBEEL: Các viên thức ăn thông thường, về bản chất là các biến Boolean cho từng chấm, như lúc trước.
Anything else?
Còn gì nữa không?
Pac-Man location. So Pac-Man xy. Anything else?
Vị trí của Pac-Man. Tức là Pac-Man xy. Còn gì nữa không?
Over there.
Bạn ở đằng kia.
STUDENT
[INAUDIBLE] PIETER ABBEEL: So that's a good question. So it depends on how this world works what we might have to put into the state space. So and I didn't really specify much about that.
[KHÔNG NGHE RÕ] PIETER ABBEEL: Đó là một câu hỏi hay. Điều cần đưa vào không gian trạng thái phụ thuộc vào thế giới này vận hành thế nào. Điều cần đưa vào không gian trạng thái phụ thuộc vào thế giới này vận hành thế nào. Mà thầy chưa nói rõ về điều đó.
Anything else?
Còn gì nữa không?
What's a good way to check if this is enough? And then we can also later check if it's maybe too much. Good way to check is what do we need from our state space?
Làm sao kiểm tra xem thế này đã đủ chưa? Và sau đó ta cũng có thể kiểm tra xem có thừa không. Cách kiểm tra tốt là hỏi: ta cần gì từ không gian trạng thái?
We need to be able to do a goal check. Like, did we satisfy the goal? OK. Goal is to eat all food pellets.
Ta cần kiểm tra được đích. Tức là, ta đã đạt đích chưa? Được. Đích là ăn hết các viên thức ăn.
Well, we can definitely check for that.
Ta chắc chắn kiểm tra được điều đó.
Then, what else is kind of part of our goal in some sense is to keep the ghosts scared at all times.
Rồi, một phần khác của đích là luôn giữ cho ma sợ hãi.
The way we think of that is that the successor function will essentially say there's nothing left in the game here if the ghosts are not scared. That game is over.
Ta xem điều đó như sau: hàm kế thừa sẽ coi như không còn gì để chơi tiếp nếu ma không còn sợ hãi. Ván chơi kết thúc.
So it's like a game over successor state. OK? And so to able to have that game over successor state, we need the timer on the ghosts.
Tức là một trạng thái kế thừa kiểu game over. Được chứ? Để có trạng thái kế thừa game over đó, ta cần bộ đếm thời gian của ma.
Otherwise, we don't know when that's going to happen. To be able to know when we reset that timer, we need to know the remaining power pellet locations.
Nếu không, ta không biết khi nào nó xảy ra. Để biết khi nào đặt lại bộ đếm đó, ta cần biết các vị trí power pellet còn lại.
Of course, we need to know where Pac-Man is relative to them. Otherwise, we can't encode whether or not these things get eaten or not. So it seems like we need all of these.
Tất nhiên, ta cũng cần biết Pac-Man đang ở đâu so với chúng. Nếu không, ta không thể mã hóa việc những thứ này có bị ăn hay không. Vậy có vẻ ta cần tất cả những thứ này.
The food palettes we need for the goal test. And the other three we need for the successor function in coding what's going to happen next when we take an action.
Các viên thức ăn cần cho việc kiểm tra đích. Còn ba thứ kia cần cho hàm kế thừa, để mã hóa điều sẽ xảy ra tiếp theo khi ta thực hiện một hành động.
And then ghosts locations, well, it's a good one. It kind of depends on how we specify the problem.
Còn vị trí của ma thì là một điểm hay. Nó tùy vào cách ta mô tả bài toán.
In Pac-Man, if you run into a scared ghost, what often happens is that it responds alive unscared.
Trong Pac-Man, nếu bạn đụng phải một con ma đang sợ hãi, thường thì nó hồi sinh trong trạng thái hết sợ.
In which case, you want that never to happen because you're supposed to be always keeping the ghosts scared. And so then you need to keep track of the ghost locations.
Khi đó, ta muốn điều này không bao giờ xảy ra vì ta phải luôn giữ cho ma sợ hãi. Và như vậy ta cần theo dõi vị trí của ma.
If you ignore them, if you say, OK, we're just going to ignore that ghosts respawn unscared, we'll just use the timer as our reference, if we say that's how the world works, then we don't need to keep track of it.
Nếu bỏ qua, nếu ta nói: được rồi, ta bỏ qua việc ma hồi sinh hết sợ, ta chỉ dùng bộ đếm thời gian làm chuẩn, nếu ta nói thế giới vận hành như vậy, thì ta không cần theo dõi chúng.
And that will often be a question you have to ask yourself about the problem you're trying to solve. Exactly how does this work? And what's the right model?
Và đây thường là câu hỏi các em phải tự đặt ra về bài toán mà mình định giải. Chính xác thì nó vận hành thế nào? Và mô hình đúng là gì?
On the slides, we kind of assume that the ghosts don't respawn alive.
Trên slide, ta giả định rằng ma không hồi sinh trong trạng thái sống lại.
But if you thought they were responding alive, then the right model would be to also keep track of the ghost locations because you'll need to simulate that process in your successor function.
Nhưng nếu các em nghĩ chúng hồi sinh, thì mô hình đúng là cũng phải theo dõi vị trí của ma vì ta cần mô phỏng quá trình đó trong hàm kế thừa.
Now, one thing that might be worth highlighting here.
Còn một điều đáng nhấn mạnh ở đây.
When we think about — let's say food pellets — why don't we just keep track of the number of food pellets left rather than going into all the details of the locations?
Khi ta nghĩ về — giả sử các viên thức ăn — sao ta không chỉ theo dõi số viên thức ăn còn lại thay vì đi vào chi tiết các vị trí?
STUDENT
If you only kept track of the number, you wouldn't really be able to do planning.
Nếu chỉ theo dõi số lượng, thì ta không thể lập kế hoạch được.
PIETER ABBEEL
Exactly.
Chính xác.
So it's important that we don't just pay attention to what the goal check asks us for, but also we need to do the planning, which is a successor function that reasons about the world.
Vậy không chỉ chú ý đến điều mà việc kiểm tra đích yêu cầu, mà còn phải lập kế hoạch, tức là hàm kế thừa phải suy luận về thế giới.
And so whenever you do any of those, think about, can I check for the goal that's needed in this state? And then, can I encode my successor function using this representation?
Nên mỗi khi làm việc này, hãy nghĩ: tôi có kiểm tra được đích từ trạng thái này không? Và tôi có mã hóa được hàm kế thừa bằng cách biểu diễn này không?
And then, check if there's anything that you didn't need. Anything here that we don't need? Not really. We needed everything that was listed, so we can't discard anything from here.
Rồi kiểm tra xem có thứ gì không cần thiết không. Ở đây có gì ta không cần không? Không hẳn. Ta cần mọi thứ đã liệt kê, nên không bỏ được thứ nào.
OK so at this point, what we looked at is how the formulate real world problems into search problems.
Vậy đến đây, điều ta đã xem là cách biến các bài toán thực tế thành bài toán tìm kiếm.
And what results from those formulations is essentially a state space graph, which is a mathematical representation of a search problem where the nodes are abstracted world configurations might look something like this.
Và kết quả của các cách mô hình hóa đó về cơ bản là một đồ thị không gian trạng thái, là một biểu diễn toán học của bài toán tìm kiếm, trong đó các nút là những cấu hình thế giới được trừu tượng hóa, và nó có thể trông giống như thế này.
And the arcs represent the successor function.
Các cung biểu diễn hàm kế thừa (successor function).
And the goal test would correspond to some of the nodes in this graph meeting the goal condition, and other ones wouldn't meet the goal condition.
Còn kiểm tra đích sẽ ứng với việc một số nút trong đồ thị này thỏa điều kiện đích, và những nút khác thì không thỏa điều kiện đích.
Now in the state space graph, every state will occur only once. Keep that in mind. We'll soon see things where that's not the case.
Trong đồ thị không gian trạng thái, mỗi trạng thái chỉ xuất hiện một lần. Hãy nhớ điều này. Sắp tới ta sẽ thấy những trường hợp không như vậy.
And we can barely build this thing in practice, so remember that we had something like to 2 to the thirtieth possible food pellet configurations for even this small world.
Và trong thực tế ta hầu như không thể xây dựng nó, vì hãy nhớ là ta có khoảng 2 mũ 30 cấu hình các viên thức ăn có thể có, dù chỉ với thế giới nhỏ này.
Well, it's very difficult to draw 2 to the thirtieth different states on a slide or even a bigger piece of paper.
Rất khó để vẽ 2 mũ 30 trạng thái khác nhau lên một slide hay thậm chí một tờ giấy lớn hơn.
And so this is really just an abstract idea for us to think about. We know it mathematically exists.
Vì vậy đây thực chất chỉ là một ý tưởng trừu tượng để ta suy nghĩ. Ta biết về mặt toán học nó tồn tại.
We're never actually going to lay this thing out unless on a slide to explain the principles behind some algorithms. Here's another one, and here's the running example we'll use.
Ta sẽ không bao giờ thật sự dựng nó ra, trừ khi trên slide để giải thích các nguyên lý đằng sau một số thuật toán. Đây là một ví dụ khác, và là ví dụ xuyên suốt ta sẽ dùng.
This is a really, really, really small state space graph research problem, and we'll use it as our running example. But keep in mind when we use this that this is just to illustrative purposes.
Đây là một bài toán tìm kiếm trên đồ thị không gian trạng thái rất, rất nhỏ, và ta sẽ dùng nó làm ví dụ xuyên suốt. Nhưng hãy nhớ rằng khi dùng nó, đây chỉ là để minh họa.
In practice, you would never first draw a state space graph and then solve the problem. You would only implicitly ever deal with this state space graph.
Trong thực tế, bạn sẽ không bao giờ vẽ đồ thị không gian trạng thái trước rồi mới giải bài toán. Bạn chỉ làm việc với đồ thị không gian trạng thái này một cách ngầm định.
What we're actually going to build up when an algorithm runs is called a search tree.
Thứ ta thực sự xây dựng dần khi thuật toán chạy được gọi là cây tìm kiếm.
Search tree is something that starts with wherever the start state is and then calls a successor function to see what's possible from there. And it might call the successor function again, and so forth.
Cây tìm kiếm bắt đầu từ trạng thái xuất phát, rồi gọi hàm kế thừa để xem từ đó có những khả năng nào. Và nó có thể gọi lại hàm kế thừa, cứ thế tiếp tục.
So the entire search tree has all possible plans in it, all possible sequences of actions, and their possible consequences.
Vậy toàn bộ cây tìm kiếm chứa mọi kế hoạch có thể, mọi chuỗi hành động có thể, và các hệ quả có thể của chúng.
In a search tree, when we think about a node in the search tree, we actually think of it as a sequence of states that have happened.
Trong cây tìm kiếm, khi nghĩ về một nút, thực ra ta xem nó như một chuỗi các trạng thái đã xảy ra.
So this node here in the search tree corresponds to starting in the start state, taking the action east, ending up in the state shown there.
Nút này trong cây tìm kiếm ứng với việc bắt đầu ở trạng thái xuất phát, thực hiện hành động đi về phía đông, và kết thúc ở trạng thái hiển thị ở đó.
For most problems we'll look at, we can't build the search tree either.
Với hầu hết các bài toán ta xét, ta cũng không thể xây dựng cây tìm kiếm. cũng vậy.
In fact, the search tree will typically be much larger even than the state space graph because there might be multiple ways to get to the same state.
Thực tế, cây tìm kiếm thường lớn hơn nhiều so với đồ thị không gian trạng thái, vì có thể có nhiều cách để đến cùng một trạng thái.
And in that case, the search tree will have multiple occurrences of that same state.
Khi đó, cây tìm kiếm sẽ có nhiều lần xuất hiện của cùng trạng thái ấy.
And so, often, it's much, much bigger than the state space graph, but it is the underlying abstraction we're going to work with.
Vì vậy nó thường lớn hơn rất nhiều so với đồ thị không gian trạng thái, nhưng nó là phần trừu tượng nền tảng mà ta sẽ làm việc cùng.
So here for our very small example, on the left is the state space graph. On the right is a search tree.
Với ví dụ rất nhỏ của ta, bên trái là đồ thị không gian trạng thái. Bên phải là cây tìm kiếm.
Assuming start state is S, search tree is rooted in the start state, and then from there, looks at all possible consequences of actions.
Giả sử trạng thái xuất phát là S, cây tìm kiếm có gốc là trạng thái xuất phát, rồi từ đó xét mọi hệ quả có thể của các hành động.
Again, we're never going to construct any one of those when we actually write code and solve real problems, but on the slides for illustrative purposes, we will have them.
Một lần nữa, ta sẽ không bao giờ dựng những thứ này khi viết code và giải các bài toán thực tế, nhưng trên slide, để minh họa, ta sẽ vẽ chúng.
Key will be in our algorithms that will construct these on-demand as needed, rather then ahead of time. OK, let's do a quick quiz. Here is a four state space graph.
Điểm mấu chốt là các thuật toán của ta sẽ dựng chúng theo yêu cầu, khi cần, thay vì dựng trước. Được rồi, làm một câu đố nhanh. Đây là đồ thị không gian trạng thái có bốn trạng thái.
What would the search tree look like for this state space graph and how big would it be?
Cây tìm kiếm của đồ thị này trông như thế nào và nó lớn cỡ nào?
I'll give you 30 seconds to talk to your neighbor and we'll see where you come up with.
Các em có 30 giây trao đổi với bạn bên cạnh rồi xem các em nghĩ ra gì.
[SIDE CONVERSATIONS] What do we think?
[CÁC CUỘC TRÒ CHUYỆN RIÊNG] Các em nghĩ sao?
Any thoughts on how big the search tree is for this state space graph? Over there.
Ai có ý kiến về kích thước của cây tìm kiếm cho đồ thị không gian trạng thái này không? Bạn ở đằng kia.
STUDENT
Infinite.
Vô hạn.
PIETER ABBEEL
Answer — infinite. Anybody wants to throw something else out than infinite? We're all going with infinite? Infinite is a good choice.
Đáp án: vô hạn. Có ai muốn đưa ra đáp án nào khác ngoài vô hạn không? Tất cả cùng chọn vô hạn à? Vô hạn là lựa chọn tốt.
Why is this infinite? Well, think about how do you build a search tree. You started at S. You can go to A or B.
Tại sao lại vô hạn? Hãy nghĩ xem bạn xây cây tìm kiếm thế nào. Bạn bắt đầu ở S. Bạn có thể đi đến A hoặc B.
From A, you could go to B or G. From B, you could go to A or G, or you can go to B or G. And even just this first path in the search tree is already infinitely long, not to mention that there is even more of them here.
Từ A, bạn có thể đến B hoặc G. Từ B, bạn có thể đến A hoặc G, hoặc đến B hoặc G. Và chỉ riêng đường đi đầu tiên này trong cây tìm kiếm đã dài vô hạn rồi, chưa kể ở đây còn nhiều đường nữa.
So what we see here is that we end up with an infinite search tree, even though the state space graph is actually quite small.
Vậy ta thấy rằng ta có một cây tìm kiếm vô hạn, dù đồ thị không gian trạng thái thực ra khá nhỏ.
So let's look at an algorithm on how to build up this search tree in a very incremental way, just enough to find a solution and then stop and return the solution.
Giờ hãy xem một thuật toán xây dựng cây tìm kiếm này theo cách tăng dần, vừa đủ để tìm ra lời giải rồi dừng lại và trả về lời giải.
Let's do an example. We'll do pathing for Romania. What does a search tree look like? Well, as you run search, you start with the start states.
Làm một ví dụ. Ta sẽ tìm đường ở Romania. Cây tìm kiếm trông như thế nào? Khi chạy tìm kiếm, bạn bắt đầu từ các trạng thái xuất phát.
You then expand out to potential next states. These are potential plans. These are one action plans. Then there is two action plans living here, and so forth.
Rồi bạn mở rộng ra các trạng thái kế tiếp tiềm năng. Đây là các kế hoạch tiềm năng. Đây là các kế hoạch một hành động. Rồi có các kế hoạch hai hành động ở đây, và cứ thế.
And the hope is that somehow we want to explore as little as possible of this giant search tree, yet find the solution.
Hy vọng là ta muốn khám phá càng ít càng tốt cái cây tìm kiếm khổng lồ này, mà vẫn tìm ra lời giải.
So it would go tier by tier, and we hope that we find a solution relatively quickly before we've traversed everything in the search tree. Here's an algorithm to do this.
Nên nó sẽ đi từng tầng một, và ta hy vọng tìm được lời giải khá nhanh trước khi ta duyệt hết mọi thứ trong cây tìm kiếm. Đây là một thuật toán để làm việc này.
It's called tree search. It will be the foundation of what we'll be doing this and next lecture. How does it work? Initialize your search tree with just the initial state of the problem.
Nó gọi là tree search. Nó sẽ là nền tảng cho những gì ta trong bài này và bài tiếp theo. Nó hoạt động thế nào? Khởi tạo cây tìm kiếm chỉ với trạng thái ban đầu của bài toán.
That's the only thing you put in it, and then you loop. You check. If there are no candidates for expansion — what's a candidate for expansion?
Đó là thứ duy nhất bạn đưa vào, rồi bạn lặp. Bạn kiểm tra. Nếu không còn ứng viên nào để mở rộng — ứng viên để mở rộng là gì?
You look at all the leaves of your search tree. Those are all candidates for expansion. If there are a non-zero number of leaves, that means you have candidates for expansion.
Bạn nhìn tất cả các lá của cây tìm kiếm. Tất cả chúng đều là ứng viên để mở rộng. Nếu số lá khác không, nghĩa là bạn có ứng viên để mở rộng.
If there are none of them, that means you only have dead ends left in your search tree, and you're done, and you didn't find a solution.
Nếu không có lá nào, nghĩa là cây tìm kiếm của bạn chỉ còn các ngõ cụt, thế là xong, và bạn không tìm được lời giải.
But if there are candidates, leaf nodes, then we pick one according to some strategy. We still have to determine that strategy, but will have many options, and somehow we'll pick one.
Nhưng nếu có ứng viên, tức các nút lá, thì ta chọn một nút theo một chiến lược nào đó. Ta vẫn phải xác định chiến lược đó, nhưng sẽ có nhiều lựa chọn, và bằng cách nào đó ta chọn một nút.
Then we'll check. If that node is a plan that ends up in one of the goals states, then you return the corresponding solution, and you're done.
Rồi ta kiểm tra. Nếu nút đó là một kế hoạch kết thúc ở một trạng thái đích, thì bạn trả về lời giải tương ứng, và xong.
If not, then you call the successor function on the last state on that node, and expand from there, and go back around. What are the key ideas?
Nếu không, bạn gọi hàm kế tiếp trên trạng thái cuối của nút đó, mở rộng từ đó, rồi quay lại vòng lặp. Các ý chính là gì?
There is the fringe, which is a set of leaf nodes that are waiting to be expanded.
Có biên (fringe), là tập các nút lá đang chờ được mở rộng.
There is the process of expansion, where you pick one out of the fringe and expand it, but before you do, of course, you check if it might already achieved the goal.
Có quá trình mở rộng, khi bạn chọn một nút từ biên và mở rộng nó, nhưng trước đó, dĩ nhiên, bạn kiểm tra xem nó đã đạt đích chưa.
And then there is the strategy. Which one of the elements in the fringe are you going to pick first to expand? And there's a lot of different strategies we'll look at.
Và cuối cùng là chiến lược. Bạn sẽ chọn phần tử nào trong biên để mở rộng trước? Và ta sẽ xem rất nhiều chiến lược khác nhau.
Let's run through an example. So how do we do this? We start with the start state and I will have two things going on.
Ta cùng chạy một ví dụ. Vậy ta làm thế nào? Ta bắt đầu với trạng thái đầu và tôi sẽ trình bày hai thứ song song.
On the left, I will expand the search tree, and on the right, this is what will be in code happening for your projects.
Bên trái là cây tìm kiếm được mở rộng, còn bên phải là thứ sẽ diễn ra trong code cho các project của bạn.
So how does this start? There is just S, and you'll just have S on your fringe. So this is the fringe, S, stored in your code, and this is the search tree.
Vậy bắt đầu thế nào? Chỉ có S, và biên của bạn chỉ có S. Đây là biên, S, được lưu trong code, và đây là cây tìm kiếm.
Well, what can we do? We only have one option, so we pick S. What happens after S? We can end up in D, E, or P.
Vậy ta làm gì được? Chỉ có một lựa chọn, nên ta chọn S. Sau S thì sao? Ta có thể đến D, E hoặc P.
The way we'll denote that here is that S got expanded, got taken out of the fringe, and instead we have S to D, S to E, S to P. Now, we again look at our fringe.
Ta ký hiệu ở đây là S được mở rộng, bị lấy ra khỏi biên, và thay vào đó ta có S tới D, S tới E, S tới P. Giờ ta lại nhìn biên.
Pick one. Which one do you want to pick? I'm hearing E. Let's go with E. We pick E from our fringe — first step.
Chọn một nút. Bạn muốn chọn nút nào? Tôi nghe thấy E. Chọn E. Ta chọn E từ biên — bước đầu tiên.
So pick this one here, which corresponds to this one here. We say, OK, does this achieve the goal condition? No. Then we expand.
Chọn nút này ở đây, tương ứng với nút này ở đây. Ta hỏi, nó có thỏa điều kiện đích không? Không. Vậy ta mở rộng.
What does it expand to?
Nó mở rộng ra đâu?
From E we can go to H or R. So we expand to H or R. In your code, this one would have disappeared, and you'd have S to E to H, and S to E to R.
Từ E ta đi được tới H hoặc R. Vậy ta mở rộng ra H hoặc R. Trong code, nút này sẽ biến mất, và bạn có S tới E tới H, và S tới E tới R.
Now, our fringe in it has four members. Which one do you want to pick?
Giờ biên của ta có bốn phần tử. Bạn muốn chọn cái nào?
Any preference? People choosing H. Interesting choice, because the goal is here. But that's a strategy.
Có ai thích cái nào không? Mọi người chọn H. Lựa chọn thú vị, vì đích ở đây. Nhưng đó là một chiến lược.
That's a thing, and we hope that in the future our computer programs will have good strategies. So H. From H we can end up in P or Q.
Cứ vậy đi, và ta hy vọng sau này chương trình máy tính của ta sẽ có chiến lược tốt. Vậy H. Từ H ta đến được P hoặc Q.
And here, the way it would look is that this would disappear from the fringe, and instead we'd have S to E to H to P. S to E to H to Q.
Và ở đây, nó sẽ trông như thế này: nút này biến mất khỏi biên, và thay vào đó ta có S tới E tới H tới P. S tới E tới H tới Q.
What do we pick next? Q. We're really going down a rabbit hole here. We're picking Q next. It is a strategy.
Tiếp theo ta chọn gì? Q. Ta đang đi sâu vào hang thỏ rồi đấy. Ta chọn Q tiếp theo. Đó là một chiến lược.
It's this year's 188 strategy. So we pick Q. Is it at the goal? No. So then we expand.
Đó là chiến lược 188 của năm nay. Vậy ta chọn Q. Nó là đích chưa? Chưa. Vậy ta mở rộng.
Does it have successors? Actually, it doesn't have any successors. So this kind of just dies off here. Nothing can happen from here.
Nó có nút kế tiếp không? Thực ra là không có. Nên nhánh này cứ thế chết ở đây. Từ đây không đi tiếp được.
With pick this off, and fringe had one less in it. We need to pick again. What do we pick next?
Ta bỏ nút này đi, và biên bớt đi một phần tử. Ta cần chọn lại. Tiếp theo ta chọn gì?
STUDENT
R.
R.
STUDENT
R.
R.
PIETER ABBEEL
Let's pick R, because search trees are very big. If we build the entire search tree, even for this problem, it's going to take a long time. So let's try to be effective.
Chọn R, vì cây tìm kiếm rất lớn. Nếu ta xây toàn bộ cây tìm kiếm, kể cả cho bài toán này, sẽ mất rất nhiều thời gian. Nên ta hãy làm cho hiệu quả.
R seems a pretty good choice. From R we can end up in F. Over here, it means that this guy disappears, and instead we have S to E to R to F.
R có vẻ là lựa chọn khá tốt. Từ R ta đến được F. Ở bên này, nghĩa là nút này biến mất, và thay vào đó ta có S tới E tới R tới F.
What do we pick next? I hear many. Let's do F, among the many choices.
Tiếp theo ta chọn gì? Tôi nghe nhiều đáp án. Ta chọn F, trong số nhiều lựa chọn.
F allows us to get to G and to C. This one goes off.
F cho phép ta đến G và C. Nút này bỏ đi.
We have S to E to R to F to G. S to E to R to F to C.
Ta có S tới E tới R tới F tới G. S tới E tới R tới F tới C.
At this point in our algorithm, we do not declare success. You might say, why not? We found a path.
Tới điểm này của thuật toán, ta không tuyên bố thành công. Bạn có thể hỏi, sao lại không? Ta đã tìm được một đường đi.
It'll matter in the future that we don't, and it's one of the most frequently occurring bugs in your project one that you declare success at this point. It's too soon.
Việc ta không làm vậy sẽ quan trọng sau này, và đó là một trong những lỗi xuất hiện thường xuyên nhất trong project của bạn: tuyên bố thành công ngay tại điểm này. Còn quá sớm.
That's not how the algorithm works. We wait. We go to our fringe again and look for candidates for expansion. What might we pick?
Thuật toán không hoạt động như vậy. Ta chờ. Ta quay lại biên và tìm các ứng viên để mở rộng. Ta có thể chọn nút nào?
Well, let's pick the one that ends in G. We pick it for expansion. We check, does it achieve the goal? The answer is, yes. Now, we declare success.
Ta hãy chọn nút kết thúc bằng G. Ta chọn nó để mở rộng. Ta kiểm tra: nó có đạt mục tiêu không? Câu trả lời là có. Bây giờ ta tuyên bố thành công.
It's not going to be obvious if you haven't seen search before why this is important, the sequencing, but it will start mattering and you will see soon why.
Nếu chưa từng học về tìm kiếm thì sẽ chưa thấy ngay vì sao thứ tự này quan trọng, nhưng nó sẽ quan trọng và các em sẽ sớm hiểu lý do.
So at this point we expanded this one, which is this one here. We declare success, and we found S to E to R to F to G as our path.
Vậy lúc này ta đã mở rộng nút này, chính là nút ở đây. Ta tuyên bố thành công, và tìm được đường đi S đến E đến R đến F đến G.
Great, we did it. Here is a — on the slides, type set version — the same thing. A slightly faster version than what we chose.
Tuyệt, ta làm được rồi. Đây là phiên bản dàn trang trên slide, của cùng một việc. Nó nhanh hơn một chút so với cách ta đã chọn.
It also highlights the actual search tree. So the actual search tree is a lot bigger than the part that needs to be explored to find a solution.
Nó cũng làm nổi bật cây tìm kiếm thực sự. Cây tìm kiếm thực sự lớn hơn nhiều so với phần cần khám phá để tìm ra lời giải.
Let's take a two minute break here. And after the break, let's explore different strategies to choose nodes for expansion.
Ta nghỉ giải lao hai phút. Sau giờ nghỉ, ta sẽ khám phá các chiến lược khác nhau để chọn nút mở rộng.
[SIDE CONVERSATIONS] Let's restart.
[NÓI CHUYỆN RIÊNG] Ta bắt đầu lại nhé.
Any questions about the first half?
Có câu hỏi nào về nửa đầu không?
Let's look at our first choice of strategy, depth-first search. Who here has seen depth-first? Many of you.
Ta xem chiến lược đầu tiên, tìm kiếm theo chiều sâu. Ai đã học tìm kiếm theo chiều sâu rồi? Khá nhiều bạn.
So it should be a good review that will ground everything else we're going to see in something you already know. If you haven't seen it, we're not going to leave anything out.
Vậy đây sẽ là phần ôn lại tốt, giúp neo mọi thứ ta sắp học vào điều các em đã biết. Nếu chưa học thì cũng không sao, thầy sẽ không bỏ sót gì.
This will be a full coverage of depth-first search. What would depth-first search mean for this pathing problem here?
Đây sẽ là phần trình bày đầy đủ về tìm kiếm theo chiều sâu. Với bài toán tìm đường này, tìm kiếm theo chiều sâu nghĩa là gì? ở đây?
Well, what makes depth-first depth-first? It's the choice of which node to expand first from the fringe. Initially there's only one node, S. So no choice has to be made.
Điều gì làm nên chiều sâu của nó? Đó là cách chọn nút nào trên biên để mở rộng trước. Ban đầu chỉ có một nút, S. Nên không cần chọn.
Every search algorithm will do the same thing. Every strategy expands S. Now we have three choices. Which one to pick?
Thuật toán tìm kiếm nào cũng làm như vậy. Chiến lược nào cũng mở rộng S. Bây giờ ta có ba lựa chọn. Chọn nút nào?
Depth-first says, pick the deepest one first. They're all equally deep. So we need to break some ties, maybe break ties alphabetically and pick D first.
Tìm kiếm theo chiều sâu nói: chọn nút sâu nhất trước. Chúng sâu như nhau. Nên ta phải phá hòa, chẳng hạn theo thứ tự bảng chữ cái, và chọn D trước.
Now on the fringe we have five candidates. The depth-first search says, pick the deepest one first. There's three deepest ones. We'll break ties, alphabetically again, expand out one.
Giờ trên biên có năm ứng viên. Tìm kiếm theo chiều sâu nói: chọn nút sâu nhất trước. Có ba nút sâu nhất. Ta lại phá hòa theo bảng chữ cái, mở rộng một nút.
Now, there is, again, five on the fringe. Depth-first search, we'll pick the deepest one first. There's only one deepest one.
Giờ lại có năm nút trên biên. Tìm kiếm theo chiều sâu sẽ chọn nút sâu nhất trước. Chỉ có một nút sâu nhất.
The only choice is to pick this node over here, which encodes going from S to D to B to A. As always in tree search, you check, did it achieve the goal?
Lựa chọn duy nhất là nút ở đây, biểu diễn đường đi từ S đến D đến B đến A. Như mọi khi trong tìm kiếm trên cây, ta kiểm tra xem nó có đạt mục tiêu không.
It did not. Then call the successor function. It has no successors, and this has been explored, and nothing left there. Four left on the fringe.
Không. Rồi gọi hàm sinh nút kế tiếp. Nó không có nút kế tiếp, vậy là đã khám phá xong, và không còn gì ở nhánh đó. Còn bốn nút trên biên.
Pick the deepest one. Again, there is ties. We pick one of them, we break ties alphabetically here, and this process kind of repeats.
Chọn nút sâu nhất. Lại có nhiều nút hòa nhau. Ta chọn một nút, phá hòa theo bảng chữ cái, và quá trình này cứ lặp lại.
Streaking left to right, if we do alphabetical tie-breaking, through this search tree until it decides to expand the goal state, at which point it's done.
Nếu phá hòa theo bảng chữ cái, nó quét từ trái sang phải qua cây tìm kiếm này cho đến khi quyết định mở rộng trạng thái đích, lúc đó nó kết thúc.
One possible strategy — depth-first. Now let's think about the properties of this algorithm, and let's first take a step back.
Một chiến lược khả dĩ: tìm kiếm theo chiều sâu. Giờ ta xét các tính chất của thuật toán này, nhưng trước hết lùi lại một bước.
What are properties we might want to quantify about any algorithm, not just depth-first search? Well, one is completeness. Is an algorithm guaranteed to find the solution, if one exists?
Ta muốn định lượng những tính chất nào của một thuật toán bất kỳ, không riêng tìm kiếm theo chiều sâu? Thứ nhất là tính đầy đủ (completeness). Thuật toán có đảm bảo tìm ra lời giải nếu có tồn tại không?
Another one is optimality. Is it guaranteed to find an optimal path, the least cost path, if one exists?
Thứ hai là tính tối ưu. Nó có đảm bảo tìm ra đường đi tối ưu, tức chi phí thấp nhất, nếu có không?
Time complexity — how long does the compute take to find a solution? And space complexity — how much memory do you need in the process of that compute to get the computation done?
Độ phức tạp thời gian: tính toán mất bao lâu để tìm ra lời giải? Và độ phức tạp không gian: cần bao nhiêu bộ nhớ trong quá trình tính toán đó để hoàn thành phép tính?
So to do this, we'll use a cartoon of a search tree. Here's our search tree cartoon. We have a start state at the top, and from there we might expand through the successor function.
Để làm vậy, ta dùng một hình minh họa của cây tìm kiếm. Đây là hình minh họa cây tìm kiếm. Ta có trạng thái bắt đầu ở trên cùng, từ đó ta mở rộng qua hàm sinh nút kế tiếp.
And we're going to have a few variables here to quantify things. So B is the branching factor. It says — essentially saying, how many successors are there from any given node?
Ta sẽ dùng vài biến ở đây để định lượng. B là hệ số phân nhánh. Về cơ bản nó cho biết một nút bất kỳ có bao nhiêu nút kế tiếp.
And for simplicity in this cartoon, we'll assume every node has as many successors as any other node, which is B.
Và để đơn giản trong hình này, ta giả sử nút nào cũng có số nút kế tiếp bằng nhau, đó là B.
So then after one choice of action, there is B possible next states, after which we have B options in each one of them, which gives us B squared possible states after two actions, and so forth.
Vậy sau một lựa chọn hành động, có B trạng thái kế tiếp có thể, rồi ở mỗi trạng thái ta lại có B lựa chọn, cho ta B bình phương trạng thái sau hai hành động, và cứ thế.
Actually, I should be more precise. These are not states that we're counting, but nodes in the search tree. We'll assume there's some maximum depth. You cannot go deeper than a certain depth.
Thực ra nói chính xác hơn, ta không đếm trạng thái mà đếm nút trong cây tìm kiếm. Ta giả sử có một độ sâu tối đa. Không thể đi sâu hơn một độ sâu nhất định.
We'll call that M. So somehow, once you have taken M actions, there is nothing left. So that means that this entire search tree in the last layer will have B to the M nodes.
Gọi nó là M. Tức là khi đã thực hiện M hành động, thì không còn gì nữa. Điều đó nghĩa là toàn bộ cây tìm kiếm này ở tầng cuối sẽ có B mũ M nút.
Again, M in the exponent is a thing that should worry you. If M is very large, this could be a very large search tree, and you wouldn't want to explore all of it.
Một lần nữa, M ở số mũ là điều đáng lo. Nếu M rất lớn, cây tìm kiếm có thể rất lớn, và ta không muốn khám phá toàn bộ nó.
There could be solutions at various depths. For example, there might be a solution all the way at the end, but also a solution somewhere that takes less actions to get to the solution.
Lời giải có thể nằm ở nhiều độ sâu khác nhau. Ví dụ, có thể có một lời giải ở tận cuối cây, nhưng cũng có lời giải khác cần ít hành động hơn để đạt tới.
And it could be multiple ones. So in this case, there is two states that satisfy — or two nodes that achieve satisfying the goal condition.
Và có thể có nhiều lời giải. Vậy trong trường hợp này, có hai trạng thái thỏa mãn — hay đúng hơn là hai nút đạt điều kiện đích.
Number of nodes in the entire tree tends to be dominated by the number of nodes in the last layer.
Số nút trong toàn bộ cây thường bị chi phối bởi số nút ở tầng cuối cùng.
It's a little more than that, but because of the exponential growth, the last layer dominates what you have.
Thực ra nó nhiều hơn một chút, nhưng do tăng trưởng theo hàm mũ, tầng cuối chi phối toàn bộ số nút.
And so we'll say order B to M. You can make it B to the M plus 1 if you want, but that's kind of the ballpark we're working with.
Nên ta sẽ nói là cỡ B mũ M. Bạn có thể viết B mũ M cộng 1 nếu muốn, nhưng đó là mức độ xấp xỉ mà ta đang xét.
So now let's look at properties of depth-first search. What nodes does DFS expand? Well, here's our cartoon tree.
Bây giờ hãy xem các tính chất của tìm kiếm theo chiều sâu. DFS mở rộng những nút nào? Đây là cây minh họa của chúng ta.
It streaks through left to right until it finds a solution. So based on that, we can start thinking about, what work does it do?
Nó quét từ trái sang phải cho đến khi tìm thấy lời giải. Dựa vào đó, ta có thể bắt đầu nghĩ xem nó phải làm bao nhiêu việc?
What's the time complexity of depth-first search if it has to traverse this thing? Worst case, it could be the entire tree.
Độ phức tạp thời gian của tìm kiếm theo chiều sâu là bao nhiêu nếu nó phải duyệt hết cây này? Trường hợp xấu nhất có thể là toàn bộ cây.
If that solution lives all the way at the end here, it's the entire tree, so that would be a lot of work. But let's say M is finite.
Nếu lời giải nằm tận cuối cùng ở đây, thì phải duyệt cả cây, tức là rất nhiều việc. Nhưng giả sử M hữu hạn.
Then that means that worst case you need to do order B to the M amount of work. How much space does it take while doing this search?
Khi đó trong trường hợp xấu nhất ta cần làm việc cỡ B mũ M. Tìm kiếm này tốn bao nhiêu bộ nhớ?
Now we need to think about what the algorithm does. The algorithm maintains a fringe, a fringe of possible nodes for expansion.
Ta cần nghĩ xem thuật toán làm gì. Thuật toán duy trì một biên (fringe), biên gồm các nút có thể mở rộng.
Let's say we're going depth-first and we currently have gone all the way here. What's on our fringe at that moment?
Giả sử ta đi theo chiều sâu và hiện đã đi tới tận chỗ này. Lúc đó biên chứa gì?
Well, from the node above here there were a bunch of options, and the ones on the right we haven't done yet. So those are on the fringe. Actually, they will be living over here.
Từ nút phía trên đây có một loạt lựa chọn, và những nút bên phải thì ta chưa làm. Vậy chúng nằm trên biên. Thực ra chúng nằm ở bên này.
So those are on the fringe. Then the node before that will also have had a bunch of options, and these are on the fringe. This line doesn't belong.
Vậy chúng nằm trên biên. Rồi nút trước đó cũng có một loạt lựa chọn, và chúng nằm trên biên. Đường này không thuộc về đây.
Then same for the node before, and so forth. So how many is that? If we count our way to the top, it's M deep.
Nút trước nữa cũng vậy, và cứ thế. Vậy có bao nhiêu nút? Đếm lên đến đỉnh thì sâu M tầng.
So there's M such successor split points, and each of them can have B successors. So there's B times M on our fringe.
Nên có M điểm rẽ nhánh như vậy, và mỗi điểm có thể có B nút con. Vậy biên có B nhân M nút.
So that's not too bad. The space complexity of depth-first search is actually very nice. Is it complete? Will it find a solution if one exists?
Như thế không tệ lắm. Độ phức tạp không gian của tìm kiếm theo chiều sâu thực ra rất tốt. Nó có đầy đủ (complete) không? Nếu có lời giải thì nó có tìm ra không?
Can a tree be infinite? So one answer is yes. The other one is, well, might it depend on whether the tree is infinite or not? It's a good question.
Cây có thể vô hạn không? Một câu trả lời là có. Câu kia là, nó có thể phụ thuộc vào việc cây có vô hạn hay không? Câu hỏi hay đấy.
So let's assume the tree cannot be infinite. What can happen?
Giả sử cây không thể vô hạn. Chuyện gì xảy ra?
Well, the first search will streak through the entire tree, and then at some point we'll find a solution if it exists and return it. How could this tree be infinite?
Tìm kiếm theo chiều sâu sẽ quét qua toàn bộ cây, và đến một lúc nào đó sẽ tìm thấy lời giải nếu có và trả về. Làm sao cây này có thể vô hạn?
Well, we saw a state space graph with only four nodes that had an infinite tree. So definitely infinite trees exist even for small state spaces.
Ta đã thấy một đồ thị không gian trạng thái chỉ có bốn nút mà có cây vô hạn. Vậy chắc chắn có cây vô hạn ngay cả với không gian trạng thái nhỏ.
So it's complete if the tree is not infinite, if we have some finiteness assumptions. Is it optimal?
Nên nó đầy đủ nếu cây không vô hạn, tức là nếu có một số giả định về tính hữu hạn. Nó có tối ưu không?
No. It just goes left to right, and it might find whatever happens to be most left and could be pretty bad. How about breadth-first search?
Không. Nó chỉ đi từ trái sang phải, và có thể tìm ra lời giải nằm ngoài cùng bên trái mà có thể khá tệ. Còn tìm kiếm theo chiều rộng thì sao?
Breadth-first search is a different strategy, where instead of taking the deepest one, we'd take the shallowest one first. So it's like we're stripping off layer by layer what's in the search tree.
Tìm kiếm theo chiều rộng là một chiến lược khác, thay vì lấy nút sâu nhất, ta lấy nút nông nhất trước. Giống như ta bóc từng lớp của cây tìm kiếm.
So what would this look like? On the same problem, we can start with S. We have no choice. Only one to pick from the fringe, expand. Then shallowest first.
Vậy nó trông thế nào? Trên cùng bài toán đó, ta bắt đầu với S. Ta không có lựa chọn nào khác. Biên chỉ có một nút để chọn, và mở rộng nó. Rồi nút nông nhất trước.
That's breadth-first. Well, they're all equally shallow. Well, pick one, break ties alphabetically — D. How about now?
Đó là tìm kiếm theo chiều rộng. Chúng đều nông như nhau. Vậy chọn một nút, phá thế hòa theo thứ tự bảng chữ cái — D. Còn bây giờ thì sao?
Now these two are more shallow than the other ones, so they're going to be called upon first. Arbitrary breaking, let's say alphabetical, E comes first.
Hai nút này nông hơn các nút còn lại, nên chúng sẽ được gọi trước. Phá hòa tùy ý, giả sử theo bảng chữ cái, E đứng trước.
And so we go through this search tree layer by layer by layer until at some point we reach a level where we find the goal, and then at some point we can declare success.
Và ta đi qua cây tìm kiếm này từng tầng một, cho đến lúc nào đó ta tới tầng có nút đích, và khi đó ta có thể tuyên bố thành công.
So a very different way of traversing this search tree. What nodes does BFS expand if we look at our cartoon here?
Vậy là một cách duyệt cây tìm kiếm rất khác. BFS mở rộng những nút nào nếu nhìn vào cây minh họa này?
Well, essentially it would expand all the nodes until you explore this guy. So everything up here would be expanding, and then actually it would have expanded into a little bit here.
Về cơ bản nó sẽ mở rộng tất cả các nút cho đến khi khám phá nút này. Vậy mọi thứ ở phía trên đây đều được mở rộng, và thực ra nó còn mở rộng sang một chút ở đây.
Because we only declare success once you expand the goal, once you're about to expand the goal, so that's part of the tree it would have covered. So what's the time complexity then?
Vì ta chỉ tuyên bố thành công khi mở rộng nút đích, tức là khi sắp mở rộng nút đích, nên đó là phần của cây mà nó đã duyệt qua. Vậy độ phức tạp thời gian là bao nhiêu?
Well, the time complexity of visiting all of those depends on the depth of the solution. If the solution is pretty shallow, it'll find it relatively quickly.
Độ phức tạp thời gian để thăm tất cả những nút đó phụ thuộc vào độ sâu của lời giải. Nếu lời giải khá nông, nó sẽ tìm ra tương đối nhanh.
So let's call that depth of the solution S. Then time complexity would be roughly B to the S. How about space complexity?
Gọi độ sâu của lời giải là S. Khi đó độ phức tạp thời gian xấp xỉ B mũ S. Còn độ phức tạp không gian thì sao?
What do we store on the fringe in this process? Well, as we go deeper and deeper, this search tree grows. It's exponential expansion.
Trong quá trình này ta lưu gì trên biên? Càng đi sâu, cây tìm kiếm này càng lớn. Nó mở rộng theo hàm mũ.
So at the very end is when we're going to have the most in our fringe.
Nên ở ngay cuối cùng là lúc ta có nhiều nút nhất trên biên.
What we'll have on the fringe is these nodes here that have not been expanded yet, and then these also that are waiting to be expanded next.
Những gì nằm trên biên là các nút này đây chưa được mở rộng, và cả các nút này nữa đang chờ để được mở rộng tiếp theo.
How many of those are there?
Có bao nhiêu nút như vậy?
Well, we're at depth S, so it's going to be roughly order B to the S nodes that are sitting on the fringe when you expand that goal node and declare success.
Ta đang ở độ sâu S, nên khoảng cỡ B mũ S nút nằm trên biên khi bạn mở rộng nút đích đó và tuyên bố thành công.
Is it complete? Does it always find a solution if one exists?
Nó có đầy đủ (complete) không? Nó có luôn tìm ra lời giải nếu có tồn tại không?
Who thinks yes? Raise of hands. Most think yes. Yeah, because it just works through the search tree, and once a solution is there, at some point it will find it.
Ai nghĩ là có? Giơ tay nào. Đa số nghĩ là có. Đúng, vì nó duyệt qua cây tìm kiếm, và khi đã có lời giải thì sớm muộn nó cũng tìm thấy.
Is it optimal? Who thinks yes? Who thinks no? Most people think no.
Nó có tối ưu không? Ai nghĩ là có? Ai nghĩ là không? Đa số nghĩ là không.
It could be somewhat debatable. In general, it's not optimal. Maybe it depends how you define optimality. If all costs of actions are the same, it's always action cost of one.
Chỗ này cũng có thể tranh luận được. Nói chung, nó không tối ưu. Có thể còn tùy bạn định nghĩa tính tối ưu thế nào.
It is optimal, because it finds the sequence of actions that's shortest to achieve the goal.
Nếu mọi hành động có chi phí như nhau, luôn là chi phí một, thì nó tối ưu, vì nó tìm ra chuỗi hành động ngắn nhất để đạt đích.
But if your costs are different for different actions, it's not guaranteed in any way to find the cheapest sequence of actions.
Nhưng nếu các hành động có chi phí khác nhau, thì không có gì đảm bảo nó tìm ra chuỗi hành động rẻ nhất.
Let's do a little quiz on DFS versus BFS. I'll do some fun animations here. Let's see — first one.
Ta làm một bài kiểm tra nhỏ về DFS so với BFS. Tôi có vài hoạt ảnh vui ở đây. Xem nào, cái đầu tiên.
What I want to showcase here is either depth-first search or breadth-first in action.
Điều tôi muốn trình bày là tìm kiếm theo chiều sâu hoặc theo chiều rộng đang chạy.
And what we're going to show is in the state space, which is every grid square is a possible state, and green is the start, red is the goal.
Ta sẽ hiển thị trong không gian trạng thái, mà mỗi ô lưới là một trạng thái có thể, màu xanh lá là điểm xuất phát, màu đỏ là đích.
Whenever for the first time we call the successor function on a particular state, we'll highlight it.
Mỗi khi lần đầu tiên ta gọi hàm successor trên một trạng thái nào đó, ta sẽ tô sáng nó.
Let's run one of the two algorithms.
Ta chạy một trong hai thuật toán.
What's this one?
Đây là thuật toán nào?
STUDENT
Breadth-first.
Theo chiều rộng.
PIETER ABBEEL
Breadth-first, because nearby states get expanded before faraway states get expanded. How about this one?
Theo chiều rộng, vì các trạng thái ở gần được mở rộng trước các trạng thái ở xa. Còn cái này thì sao?
It did find the solution. It's not the shallowest one in the search tree — depth-first search.
Nó đã tìm ra lời giải. Nhưng không phải lời giải nông nhất trong cây tìm kiếm, đó là tìm kiếm theo chiều sâu.
Now, what if we do this in the context of some obstacles.
Giờ nếu ta làm điều này khi có vài chướng ngại vật thì sao?
So black squares are ones you cannot get through. They're walls. The blue squares are squares you can visit. Let's again see what's what.
Các ô đen là ô bạn không thể đi qua. Chúng là tường. Các ô xanh dương là ô bạn có thể đi tới. Ta lại xem nó là gì.
I'll run one of the two. You call out which one it is.
Tôi chạy một trong hai. Các bạn nói xem là cái nào.
Who says breadth-first? Everyone. Great. It was breadth-first search.
Ai nói theo chiều rộng? Tất cả mọi người. Tuyệt. Đó là tìm kiếm theo chiều rộng.
And the way you see it is that it expands from the start state out. It's not radially symmetric now, because the walls are blocking some paths.
Và bạn nhận ra vì nó lan ra từ trạng thái xuất phát. Giờ nó không đối xứng tròn nữa, vì các bức tường chặn một số đường đi.
And it's based on the length of those paths, not based on straight line distance. But this is breadth-first search. How about this one?
Nó dựa trên độ dài của các đường đi đó, chứ không dựa trên khoảng cách đường thẳng. Nhưng đây là tìm kiếm theo chiều rộng. Còn cái này thì sao?
Who thinks breadth-first? Nobody. Depth-first search? It finds a solution again, but not maybe the one you'd hoped for.
Ai nghĩ là theo chiều rộng? Không ai. Theo chiều sâu? Nó lại tìm ra lời giải, nhưng có thể không phải cái bạn mong muốn.
Might there be some trade-offs here though? When might BFS outperform DFS and the other way around? Any thoughts on when which one might be preferable? Here.
Vậy có sự đánh đổi nào ở đây không? Khi nào BFS tốt hơn DFS và ngược lại? Bạn nào có ý kiến khi nào nên dùng cái nào không? Bạn này.
STUDENT
If the — if we're thinking in terms of a tree, if the goal is shallow and to the right, it would be [INAUDIBLE].
Nếu xét theo cây, nếu đích nằm nông và lệch về bên phải thì sẽ [KHÔNG NGHE RÕ]. [KHÔNG NGHE RÕ].
PIETER ABBEEL
So the suggestion was if the goal is shallow and to the right in the tree, BFS will drastically outperform DFS, which will sweep the entire tree before finally getting there.
Ý kiến là nếu đích nằm nông và lệch bên phải của cây, BFS sẽ vượt trội hẳn DFS, vì DFS sẽ quét cả cây rồi mới tới được đó.
Yeah, definitely a big advantage there for BFS. Any other thoughts about trade-offs?
Đúng, rõ ràng đó là một lợi thế lớn của BFS. Còn ý kiến nào về sự đánh đổi nữa không?
Here.
Bạn này.
STUDENT
All of these examples, we've only had one goal. But if you had many satisfiable outcomes, they're all in our way, then you'd want to do a depth-first search.
Trong các ví dụ này ta chỉ có một đích. Nhưng nếu có nhiều kết quả thỏa mãn, nằm đầy trên đường đi, thì bạn sẽ muốn dùng tìm kiếm theo chiều sâu.
PIETER ABBEEL
So the suggestion is that maybe when there is many, many goals in the tree, and they're all very deep — so you need to go deep anyway — then maybe depth-first search will find them first, because breadth-first will be so busy before it finally is willing to look at anything at the bottom.
Ý kiến là có lẽ khi có rất nhiều đích trong cây, và chúng đều rất sâu, nên dù sao cũng phải đi sâu, thì có thể DFS sẽ tìm thấy chúng trước, vì BFS sẽ bận rộn mãi trước khi chịu xem xét bất cứ thứ gì ở dưới đáy.
And actually, we'll see exactly that scenario in lecture — let's see — four next week, Tuesday. So that's a nice case where DFS has the advantage.
Thật ra ta sẽ thấy đúng kịch bản đó trong bài giảng, để xem, thứ Ba tuần sau, bài bốn. Đó là một trường hợp hay mà DFS có lợi thế.
And other thoughts about trade-offs?
Còn ý kiến nào khác về sự đánh đổi không?
Over there.
Bạn đằng kia.
STUDENT
If you have memory limitations, and you can't actually use BFS [INAUDIBLE],, you'd have to use DFS.
Nếu bộ nhớ bị giới hạn, và bạn không thể dùng BFS [KHÔNG NGHE RÕ], thì bạn buộc phải dùng DFS.
PIETER ABBEEL
Yeah, so the suggestion is, if you have memory limitations, DFS is so much better in terms of memory than BFS.
Đúng, ý kiến là nếu bộ nhớ có hạn, DFS tốn bộ nhớ ít hơn BFS rất nhiều.
So maybe you just have to use it, even when maybe you want to find a shortest path. You just have no choice, because you'd run out of memory using breadth-first.
Nên có thể bạn buộc phải dùng nó, dù có thể bạn muốn tìm đường đi ngắn nhất. Bạn không có lựa chọn, vì nếu dùng BFS bạn sẽ hết bộ nhớ.
Any other thoughts? Yes.
Còn ý kiến nào khác không? Mời bạn.
STUDENT
You have [INAUDIBLE] path problem.
Bạn có bài toán đường đi [KHÔNG NGHE RÕ].
PIETER ABBEEL
So BFS has the advantage of finding the shortest path. Now let's see if we can combine some of those all in one.
BFS có lợi thế là tìm ra đường đi ngắn nhất. Giờ ta xem có thể kết hợp những ưu điểm đó vào một thuật toán không.
So we like BFS because it finds the shortest path based on counting number of actions. If a short solution exists, it doesn't spend time exploring the entire tree.
Ta thích BFS vì nó tìm ra đường đi ngắn nhất dựa trên theo số lượng hành động. Nếu tồn tại lời giải ngắn, nó không mất thời gian khám phá toàn bộ cây.
It just needs to find the short solution. But DFS has better memory properties. So can we bring them both together in one algorithm and get the benefits of all of these?
Nó chỉ cần tìm ra lời giải ngắn đó. Nhưng DFS có ưu điểm về bộ nhớ. Vậy ta có thể kết hợp cả hai trong một thuật toán và có được lợi thế của cả hai không?
It turns out we can. It's something called iterative deepening, and the idea is to get the space advantage of DFS built into a breadth-first search.
Hóa ra là có thể. Đó là iterative deepening, ý tưởng là đưa ưu thế về không gian của DFS vào tìm kiếm theo chiều rộng.
Or he can think of it the other way around, you're essentially just bringing them both together. What's the idea here?
Hoặc bạn có thể nghĩ theo chiều ngược lại, về bản chất là gộp cả hai lại với nhau. Ý tưởng ở đây là gì?
You always run depth-first search, because that's the memory efficient one and you're not willing to forego that. But you cap the depth to which you're willing to search.
Bạn luôn chạy tìm kiếm theo chiều sâu, vì nó tiết kiệm bộ nhớ và bạn không muốn từ bỏ điều đó. Nhưng bạn giới hạn độ sâu tối đa được tìm.
So your first run, when you hit depth one, you stop. Your successor function is modified to say there's nothing beyond depth one. This is it. You have to stop.
Lần chạy đầu, khi chạm độ sâu một thì dừng. Hàm sinh trạng thái kế tiếp được sửa lại để coi như không có gì bên dưới độ sâu một. Hết rồi. Bạn phải dừng.
If you don't find a solution that way, then you made the cap two. If you find a solution, that's great. You found the solution with only two steps.
Nếu không tìm được lời giải theo cách đó, thì bạn nâng giới hạn lên hai. Nếu tìm được lời giải thì tốt quá. Bạn tìm được lời giải chỉ với hai bước.
But if you don't find a solution, you made the cap three, and you keep expanding your cap. You can always run depth-first search, so you never run into memory issues.
Nhưng nếu chưa tìm được, bạn nâng giới hạn lên ba, và cứ thế tiếp tục tăng. Bạn luôn chạy tìm kiếm theo chiều sâu, nên không bao giờ gặp vấn đề về bộ nhớ.
Yet, you are also now going down rabbit holes on the far left that might lead nowhere, but be really, really big.
Đồng thời, bạn cũng không bị lạc vào những hố thỏ ở phía ngoài cùng bên trái có thể chẳng dẫn đến đâu mà lại rất, rất lớn.
Because remember, the bottom of the tree is exponentially large compared to the top, and if you spend a lot of time at the bottom, you're going to be spending a lot of time overall.
Vì hãy nhớ, phần đáy của cây lớn hơn phần đỉnh theo cấp số mũ, và nếu tốn nhiều thời gian ở đáy, thì tổng thể bạn sẽ tốn rất nhiều thời gian.
So a very simple way to solve search and getting the best of both worlds. You might wonder, is this not wastefully redundant?
Vậy đây là một cách rất đơn giản để giải bài toán tìm kiếm và được lợi thế của cả hai. Bạn có thể thắc mắc, thế này có lặp lại lãng phí không?
Am I not redoing the work for the first one every time, and the second one every time, but the first time, the third one every time, but the first two?
Chẳng phải mỗi lần ta làm lại phần của lớp thứ nhất, rồi lớp thứ hai, trừ lần đầu, lớp thứ ba, trừ hai lần đầu sao?
Yes, there is some waste happening. But if you think about it, it's not bad. And the reason it's not that bad is because the last layer is so much bigger than the previous layers.
Đúng, có một chút lãng phí. Nhưng nghĩ kỹ thì nó không tệ. Lý do nó không tệ lắm là vì lớp cuối lớn hơn nhiều so với các lớp trước.
In fact, the last layer tends to be as big as all previous layers combined.
Thật ra, lớp cuối thường lớn bằng tất cả các lớp trước cộng lại.
And so the redundant work you do is not that much compared to — you need to expand that last layer anyway to find out new results.
Nên phần việc lặp lại không đáng kể so với việc phải mở rộng lớp cuối để tìm ra kết quả mới.
That's also where this cartoon is kind of misleading, by the way. This looks like something that just grows linearly effectively with depth and size.
Nhân tiện, đây cũng là chỗ hình minh họa này dễ gây hiểu lầm. nhân tiện nói luôn. Trông như thể nó chỉ tăng tuyến tính theo độ sâu và kích thước.
The width there is linearly with that, but in practice, exponential, which we can't really draw in just two dimensions. Now let's switch gears to a different kind of problem formulation.
Chiều rộng ở đó tăng tuyến tính theo, nhưng thực tế là theo cấp số mũ, điều mà ta khó vẽ được trong hai chiều. Giờ ta chuyển sang một dạng bài toán khác.
What if we care about the cost? Not just cost one for each action, but different actions could have different costs. For example, this transition costs three. This one costs two, and so forth.
Nếu ta quan tâm đến chi phí thì sao? Không chỉ chi phí một cho mỗi hành động, mà các hành động có thể có chi phí khác nhau. Ví dụ, bước chuyển này tốn ba. Bước này tốn hai, v.v.
How do you find the shortest path accounting for cost? Uniform cost search will do that for us. So how does this work?
Làm sao tìm đường đi ngắn nhất tính theo chi phí? Uniform cost search sẽ làm được việc đó. Nó hoạt động thế nào?
It's kind of inspired by breadth-first search, which expands shallowest first, but now we'll look at least cost first. So it starts out with expanding from S.
Nó lấy cảm hứng từ tìm kiếm theo chiều rộng, vốn mở rộng nút nông nhất trước, nhưng giờ ta xét chi phí thấp nhất trước. Bắt đầu bằng việc mở rộng từ S.
We have three nodes in the fringe, and instead of picking shallowest or deepest, we pick based on lowest cost. This one has 1. This one, 9. This one, 3.
Ta có ba nút trên biên, và thay vì chọn nông nhất hay sâu nhất, ta chọn theo chi phí thấp nhất. Nút này là 1. Nút này, 9. Nút này, 3.
With pick P, we expand. Then we check again. Which is lowest, 3, 9, or 16? 3 is lowest, we expand D.
Ta chọn P, rồi mở rộng. Rồi kiểm tra lại. Cái nào thấp nhất, 3, 9 hay 16? 3 thấp nhất, ta mở rộng D.
And we repeat this process. Now what's lowest? 4 is lowest, and we expand that one. Now its lowest is 5.
Và lặp lại quy trình này. Giờ cái nào thấp nhất? 4 thấp nhất, ta mở rộng nút đó. Giờ thấp nhất là 5.
And keep in mind, this is actually cumulative cost.
Lưu ý, đây thật ra là chi phí tích lũy.
So when it says 5, that is a cost of 3 going from S to D, a cost of 2 going from D to E — cumulatively, 5.
Khi ghi 5, đó là chi phí 3 đi từ S đến D, chi phí 2 đi từ D đến E, tích lũy là 5.
And so our lowest cumulative cost on the fringes 5. That's what we expect next. The next lowest is 6. We'll go with 6 next.
Vậy chi phí tích lũy thấp nhất trên biên là 5. Đó là nút ta chọn tiếp theo. Thấp nhất kế tiếp là 6. Ta chọn 6 tiếp theo.
And we'll keep going, popping things from the fringe based on lowest cost first. Right now, lowest cost is 9 over here.
Và cứ tiếp tục lấy các nút ra khỏi biên theo chi phí thấp nhất trước. Lúc này chi phí thấp nhất là 9 ở đây.
We also see the goal sit on the fringe.
Ta cũng thấy đích nằm trên biên.
This is where it starts mattering what we do. We're always picking the lowest one. Even though the goal is there, you might say, why don't we call it quits?
Đây là lúc cách ta làm bắt đầu quan trọng. Ta luôn chọn nút thấp nhất. Dù đích đã ở đó, bạn có thể hỏi, sao không dừng luôn?
We see the goal. We call it done. We found the path. No.
Ta thấy đích rồi. Coi như xong. Ta tìm được đường đi. Không.
We still pick the one with lowest cost, 9, because you don't know.
Ta vẫn chọn nút có chi phí thấp nhất, 9, vì ta chưa biết được.
Maybe from that one with 9, there is one with cost only 0.5 that leads to the goal, and if we already declared success here with the goal, we would not have found that one.
Biết đâu từ nút 9 đó, có một nút chỉ tốn 0.5 dẫn đến đích, và nếu ta đã tuyên bố thành công với đích này, ta sẽ không tìm ra nó.
So we're still got to try this, because it's only 9 so far, and it could maybe achieve goal at a cheaper cost than the one that we see there.
Nên ta vẫn phải thử, vì hiện mới là 9, và có thể đến đích với chi phí rẻ hơn đường mà ta đang thấy ở đó.
Now the lowest cost on the fringe is 10, and it corresponds to the goal state, and we can declare success. And we're guaranteed it's optimal. Why?
Giờ chi phí thấp nhất trên biên là 10, và nó ứng với trạng thái đích, và ta có thể tuyên bố thành công. Và ta được đảm bảo đó là nghiệm tối ưu. Tại sao?
We have in the search tree explored every single path that you can traverse with a cost of 10 or less. There is nothing left you can do with a cost 10 or less.
Trong cây tìm kiếm, ta đã khám phá mọi đường đi có chi phí từ 10 trở xuống. Không còn đường nào có chi phí từ 10 trở xuống nữa.
Everything else that exists will cost you more than 10. And we found the goal with cost of 10, so we know that's the optimal way to get to the goal.
Mọi đường còn lại đều tốn hơn 10. Và ta đã tìm được đích với chi phí 10, nên ta biết đó là cách tối ưu để đến đích.
We, again, get a tiered expansion, but this time the tiering is not based just on layers, but based on cost encountered so far.
Một lần nữa, ta có kiểu mở rộng theo từng tầng, nhưng lần này các tầng không chỉ dựa trên độ sâu, mà dựa trên chi phí đã tích lũy cho đến lúc này.
Let's look at the properties. What nodes does it expand? Well, it's based on cost. So to quantify this, we'll have to say something about cost.
Hãy xem các tính chất. Nó mở rộng những nút nào? Nó dựa trên chi phí. Để định lượng, ta phải nói gì đó về chi phí.
And so if, let's say, the optimal solution is a cost C star, and each individual step costs us at least epsilon, then we might have expanded plans that take C star over epsilon actions to get there.
Giả sử nghiệm tối ưu có chi phí C sao, và mỗi bước riêng lẻ tốn ít nhất epsilon, thì ta có thể đã mở rộng các kế hoạch có C sao chia epsilon hành động để đi tới đó.
So if every action costs at least epsilon and the goal is C star, then the longest path we could get below C star is C star over epsilon.
Nếu mỗi hành động tốn ít nhất epsilon và đích có chi phí C sao, thì đường đi dài nhất mà vẫn dưới C sao có độ dài C sao chia epsilon.
So that's what we expand in the tree, anything that is less than that many actions. We will call this the "effective depth."
Vậy ta mở rộng trong cây mọi thứ có số hành động ít hơn mức đó. Ta gọi đây là "độ sâu hiệu dụng".
And so the computational cost in principle could be branching factor B to the power effective depth. So it'll be exponential in the effective depth.
Do đó chi phí tính toán về nguyên tắc có thể là hệ số nhánh B mũ độ sâu hiệu dụng. Tức là hàm mũ theo độ sâu hiệu dụng.
How much space does the fringe take? Well, what's happening? When we're expanding, for example, when we're here, and we're about to expand, let's see.
Biên chiếm bao nhiêu không gian? Chuyện gì đang xảy ra? Khi ta đang mở rộng, ví dụ khi ở đây, và sắp mở rộng, để xem nào.
So we're about to expand this one. Let's say, if this is our fringe right now here, and we're about to expand this one here, how much is on the fringe?
Ta sắp mở rộng nút này. Giả sử đây là biên của ta lúc này, và ta sắp mở rộng nút này, thì biên có bao nhiêu nút?
Well, how many nodes we can have here depends on the depth in the search tree. Our effective depth is C star over epsilon.
Số nút ở đây phụ thuộc vào độ sâu trong cây tìm kiếm. Độ sâu hiệu dụng của ta là C sao chia epsilon.
So the amount of space taken would be B to the effective depth, which is the same as our computational complexity. Is it complete? Will it always find a solution if a solution exists?
Vậy không gian tốn là B mũ độ sâu hiệu dụng, giống với độ phức tạp tính toán. Nó có đầy đủ (complete) không? Nó có luôn tìm ra nghiệm nếu nghiệm tồn tại không?
Yes, because it will systematically keep working through to search tree until it finds that path. There is some subtleties there about cost being positive and not getting looped into some negative cost cycles.
Có, vì nó sẽ có hệ thống duyệt cây tìm kiếm cho đến khi tìm thấy đường đó. Có vài điểm tinh tế về việc chi phí phải dương và không bị kẹt trong các chu trình có chi phí âm.
But assuming that's all satisfied, we're good. Is it optimal? Yes, because whenever we expand the goal state, we know there's nothing left that's cheaper than the path we just found to the goal state.
Nhưng nếu các điều đó thỏa mãn thì ổn. Nó có tối ưu không? Có, vì khi ta mở rộng trạng thái đích, ta biết không còn gì rẻ hơn đường đi vừa tìm được tới trạng thái đích.
Everything on the fringe has a higher cost, and so it can never — assuming all costs are positive — come below what we have right now as our path to the goal.
Mọi thứ trên biên đều có chi phí cao hơn, nên không bao giờ có thể, giả sử mọi chi phí đều dương, thấp hơn thứ ta đang có làm đường đi tới đích.
We'll do a formal proof with A star search, which is an extension of this in the next lecture. What are some issues? Well, it explores this increasing cost sets of nodes.
Ta sẽ chứng minh chặt chẽ với tìm kiếm A sao, một mở rộng của phương pháp này, ở bài giảng sau. Có những vấn đề gì? Nó khám phá các tập nút có chi phí tăng dần.
It's nice. It's complete and optimal. But the bad is that it explores in every direction, which could be very expensive.
Như vậy là tốt. Nó đầy đủ và tối ưu. Nhưng điểm xấu là nó khám phá mọi hướng, điều có thể rất tốn kém.
It doesn't really think about where the goal might be, and that's where the next lecture will come in, to focus your search on things that are promising rather than things that have been cheap so far.
Nó không thực sự nghĩ đến việc đích có thể ở đâu, và đó là chỗ bài giảng sau sẽ vào cuộc, để tập trung tìm kiếm vào những thứ có triển vọng thay vì những thứ đã rẻ cho đến giờ.
So uniform cost search thinks of all these things as equally good. But if you are more informed, going towards the goal would be preferable. Let's look at the demo of UCS in action.
Tìm kiếm chi phí đồng nhất coi tất cả những thứ này đều tốt như nhau. Nhưng nếu có thêm thông tin, đi về phía đích sẽ được ưu tiên hơn. Hãy xem demo UCS đang chạy.
So in this maze, black is still intraversable.
Trong mê cung này, màu đen vẫn là không thể đi qua.
There is shallow waters and there is deep waters. The dark blue is deep water, and it's more expensive to traverse, and the shallow water is the fainter blue, and it's cheaper to traverse.
Có vùng nước nông và vùng nước sâu. Màu xanh đậm là nước sâu, và đi qua tốn kém hơn, còn nước nông là màu xanh nhạt hơn, và đi qua rẻ hơn.
So if we run uniform costs search, what would we expect?
Nếu chạy tìm kiếm chi phí đồng nhất, ta mong đợi gì?
We would hope that it would spend more time in the shallow waters, because it's cheaper to expand there, but as needed, also visit the deeper waters if that turns out to be the cheapest way to get to the goal.
Ta hy vọng nó sẽ dành nhiều thời gian hơn ở vùng nước nông vì mở rộng ở đó rẻ hơn, nhưng khi cần vẫn đi vào vùng nước sâu nếu đó là cách rẻ nhất để tới đích.
Let's see what happens.
Hãy xem chuyện gì xảy ra.
We see, indeed, that it kind of blocks on the deeper water while more quickly expanding in the shallow water. Let's play this again.
Quả thật ta thấy nó như bị chặn lại ở nước sâu trong khi mở rộng nhanh hơn ở nước nông. Hãy chạy lại lần nữa.
And this is the behavior you hope for for uniform cost search.
Và đây là hành vi mà bạn hy vọng ở tìm kiếm chi phí đồng nhất.
Remember of course, if you run something like breadth-first search, it would completely ignore the shallow versus deep water.
Tất nhiên hãy nhớ, nếu chạy thứ gì đó như tìm kiếm theo chiều rộng, nó sẽ hoàn toàn bỏ qua sự khác biệt giữa nước nông và nước sâu.
It's just based on number of actions, and expansion is just as fast in the deep water versus shallow when it's doing the search.
Nó chỉ dựa trên số hành động, và việc mở rộng ở nước sâu nhanh y như ở nước nông khi nó đang tìm kiếm.
And of course, depth-first search completely ignores kind of everything, but still finds a solution.
Còn tìm kiếm theo chiều sâu thì gần như bỏ qua mọi thứ, nhưng vẫn tìm ra nghiệm.
So we'll fix this soon to pay more attention to how far you're away from the goal and target your search.
Ta sẽ sớm sửa điều này để chú ý hơn đến việc ta cách đích bao xa và nhắm mục tiêu tìm kiếm.
For this lecture, let's spend a little bit of time on unifying what we've seen so far and then show some of the limitations.
Trong bài này, hãy dành chút thời gian để thống nhất những gì đã thấy và rồi chỉ ra một số hạn chế.
So remember, when we defined a search algorithm, tree search, we had the same algorithm for DFS, BFS, and uniform cost search.
Hãy nhớ khi ta định nghĩa một thuật toán tìm kiếm, tìm kiếm trên cây, ta có cùng một thuật toán cho DFS, BFS và tìm kiếm chi phí đồng nhất.
The only thing that differed was the strategy of what to pick next from the fringe.
Điểm khác duy nhất là chiến lược chọn gì tiếp theo từ biên.
And so one way, in your project one, for example, to implement everything with essentially one piece of code is if you have a priority queue and you just use different priorities for different types of searches.
Và một cách, ví dụ trong project một, để cài đặt tất cả chỉ bằng một đoạn mã là dùng một hàng đợi ưu tiên và chỉ cần dùng các độ ưu tiên khác nhau cho các kiểu tìm kiếm khác nhau.
If it's depth-first, priority is based on how deep you are. Deeper is better. If it's breadth-first, priority is based on how shallow you are. Shallow is better.
Nếu là theo chiều sâu, ưu tiên dựa trên việc bạn sâu đến đâu. Càng sâu càng tốt. Nếu là theo chiều rộng, ưu tiên dựa trên việc bạn nông đến đâu. Càng nông càng tốt.
And if this uniform cost, priority is based on how much cost you've encountered so far on this path. So a single implementation that can unify everything. Can search go wrong?
Và nếu là chi phí đồng nhất, ưu tiên dựa trên tổng chi phí bạn đã phải trả cho đến nay trên đường đi này. Vậy là một cách cài đặt duy nhất có thể thống nhất tất cả. Tìm kiếm có thể sai không?
Well, let's look at some examples drawn from the real world. Here is MapQuest, an old path planning thing for driving. Let's take a look at one.
Chúng ta hãy xem vài ví dụ lấy từ thế giới thực. Đây là MapQuest, một công cụ lập lộ trình lái xe đời cũ. Ta xem thử một trường hợp.
It was asked to find the path to a destination, and all goes pretty well until over here it decides to take this turn, which happens to be this turn over here for your car.
Nó được yêu cầu tìm đường đến một điểm đến, và mọi thứ khá ổn cho đến đoạn này thì nó quyết định rẽ ở chỗ này, mà đó lại chính là chỗ rẽ này đây đối với xe của bạn.
It doesn't work. So what we see here is a mismatch between how the map was made and what your search problem then could work on compared to the real world.
Không đi được. Vậy ở đây ta thấy có sự không khớp giữa cách bản đồ được tạo ra và bài toán tìm kiếm của bạn có thể xử lý so với thế giới thực.
So it doesn't mean that A star failed, or uniform cost failed, or depth-first/breadth-first failed. It just means that your search problem formulation was not abstracting the world the right way.
Điều đó không có nghĩa A star thất bại, hay uniform cost thất bại, hay depth-first/breadth-first thất bại. Nó chỉ có nghĩa là cách bạn xây dựng bài toán tìm kiếm đã không trừu tượng hóa thế giới đúng cách.
Here's another example of search in action.
Đây là một ví dụ khác về tìm kiếm trong thực tế.
What's happening here?
Chuyện gì đang xảy ra ở đây?
Is this the search algorithm having a bug? It's possible, but most likely that's not what it is.
Có phải thuật toán tìm kiếm bị lỗi không? Có thể, nhưng nhiều khả năng không phải vậy.
What's going on is probably somewhere near to the destination here somehow the map is incomplete, and it lacks a way to get to the destination from this side.
Có lẽ là ở gần điểm đến này, bản đồ bằng cách nào đó bị thiếu, và không có đường đến điểm đến từ phía này.
The path is just not in the state space graph.
Đường đi đơn giản là không có trong đồ thị không gian trạng thái.
And as a consequence, when you run search, well, it's just calling successor, successor, successor, and this happens to be what it finds, which involves taking your car on a boat trip, multiple boat trips before you get there.
Kết quả là khi bạn chạy tìm kiếm, nó chỉ gọi successor, successor, successor, và đây là thứ nó tìm ra, là đưa xe của bạn đi phà, nhiều chuyến phà trước khi tới nơi.
So keep this in mind. Whenever you are doing search for real world problems, building the right models is really critical to get good results.
Hãy ghi nhớ điều này. Bất cứ khi nào bạn tìm kiếm cho các bài toán thực tế, việc xây dựng mô hình đúng là cực kỳ quan trọng để có kết quả tốt.
That's it for today. See you on Thursday.
Hôm nay đến đây thôi. Hẹn gặp lại các bạn vào thứ Năm.
[SIDE CONVERSATION]
[TRÒ CHUYỆN RIÊNG]
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.