Behavior Tree (Cây Hành Vi)
Khái niệm chính
Cây Hành Vi (Behavior Tree) là mô hình phân cấp được sử dụng trong trí tuệ nhân tạo (AI) để điều khiển việc ra quyết định và các hành vi, đặc biệt là trong robot, AI trò chơi và các hệ thống tự hành. Nó tổ chức các nhiệm vụ và hành động thành một cấu trúc cây, trong đó mỗi nút (node) đại diện cho một hành vi hoặc một quyết định.
Cây được duyệt từ trên (nút gốc - root) xuống dưới (nút lá - leaf). Mỗi nút quyết định bước tiếp theo dựa trên các điều kiện hoặc kết quả cụ thể (thành công - Success, thất bại - Failure, hoặc đang chạy - Running).
- Một tín hiệu gọi là "tick" được gửi đến nút gốc của cây và lan truyền qua các nhánh cho đến khi chạm tới nút lá.
- Bất kỳ Nút nào nhận được tín hiệu tick sẽ thực thi callback của nó. Callback này phải trả về một trong các trạng thái:
- SUCCESS (Thành công)
- FAILURE (Thất bại)
- RUNNING (Đang chạy)
- RUNNING có nghĩa là hành động cần thêm thời gian để hoàn thành và trả về kết quả cuối cùng.
- Nếu một Nút có một hoặc nhiều nút con, trách nhiệm của nó là lan truyền tín hiệu tick xuống các nút con; mỗi loại Nút có thể có các quy tắc khác nhau về việc có tick nút con hay không, khi nào tick và tick bao nhiêu lần.
- Các Nút Lá (Leaf Nodes), vốn không có nút con nào, chính là các lệnh hành động thực tế. Nút Hành động (Action) là loại Nút Lá phổ biến nhất.
Các loại Nút (Nodes)
Mỗi nút là một phần tử riêng biệt đại diện cho hành động, quyết định hoặc cơ chế điều khiển luôn chuyển. Mỗi nút đóng một vai trò trong việc định hình hành vi của AI. Có nhiều loại nút khác nhau, mỗi nút trả về một trạng thái (Success, Failure, Running) và phục vụ một mục đích riêng:
- Nút Hành động (Action nodes): Là các nút lá của cây hành vi, thực thi một nhiệm vụ hoặc hành động cụ thể như di chuyển, tấn công hoặc bật hoạt ảnh.
- Nút Điều kiện (Condition nodes): Kiểm tra một điều kiện và trả về thành công hoặc thất bại, ví dụ: kiểm tra xem người chơi có trong tầm mắt không hoặc lượng máu có thấp không.
- Nút Điều khiển (Control Nodes): Quản lý luồng thực thi của cây
- Nút Tuần tự (Sequence Node): Thực thi các nút con theo thứ tự, dừng lại nếu một nút con bị thất bại.
- Nút Dự phòng (Fallback Node / Selector Node): Thực thi các nút con theo thứ tự, dừng lại nếu một nút con thành công.
- Nút Song song (Parallel Node): Thực thi nhiều nút con cùng lúc và trả về kết quả dựa trên số lượng nút thành công.
- Nút Trang trí (Decorator Node): Chỉnh sửa hành vi của duy nhất một nút con bằng một chính sách tùy chỉnh, ví dụ: Đảo ngược (Invert), Lặp lại (Repeat / Retry), Hết giờ (Timeout), Ép thất bại (Force Failure), v.v.
Ví dụ Robot: Tìm kiếm đối tượng
Giả sử chúng ta có một robot di động cần tìm kiếm các đối tượng cụ thể trong môi trường nhà ở. Giả định rằng robot đã biết trước vị trí của tất cả các đối tượng và có thể di chuyển trong nhà.
Hãy bắt đầu đơn giản với việc robot di chuyển tới vị trí (gọi là A). Cây hành vi là một chuỗi tuần tự các hành động cần thiết: Di chuyển tới vị trí rồi tìm kiếm đối tượng.
Chúng ta chọn đại diện việc di chuyển là một nút Hành động vì robot cần thời gian di chuyển (trả về Running trong quá trình đó). Ngược lại, quan sát được đại diện là một nút Điều kiện, giả định robot có thể phát hiện đối tượng ngay từ một hình ảnh thu được khi đã tới nơi.
Một nguyên tắc thiết kế rất phổ biến là Điều kiện thành công rõ ràng (Explicit success condition), có nghĩa là bạn nên luôn kiểm tra trước khi hành động. Ví dụ: trước khi di chuyển tới một vị trí, bạn nên kiểm tra xem mình đã ở đó chưa.
Điều kiện thành công rõ ràng sử dụng một nút Fallback chứa một điều kiện đặt trước một hành động. Hành động được bảo vệ chỉ thực thi nếu điều kiện chưa thỏa mãn — trong ví dụ này là nếu robot chưa ở vị trí A.
Robot của chúng ta hoạt động trong môi trường có nhiều vị trí khác nhau, và ý tưởng là tìm kiếm ở tất cả các vị trí cho tới khi tìm thấy đối tượng mong muốn. Điều này thực hiện bằng cách thêm một nút Fallback ở cấp gốc và lặp lại hành vi trên cho từng vị trí theo một thứ tự nhất định.
Cuối cùng, giả sử thay vì tìm kiếm một đối tượng duy nhất, chúng ta muốn tìm kiếm nhiều đối tượng — chẳng hạn cả táo và cam. Việc kết hợp nhiều điều kiện có thể dùng nút Song song (Parallel node) như dưới đây.
- Nếu chúng ta chấp nhận quả táo hoặc quả cam (điều kiện "HOẶC"), cây thành công nếu một nút con trả về Success.
- Nếu chúng ta yêu cầu phải có cả táo lẫn cam (điều kiện "VÀ"), cây thành công khi cả hai nút con trả về Success.
- Nếu chúng ta quan tâm tới thứ tự (ví dụ phải tìm thấy táo trước rồi mới tìm cam), ta có thể thay thế bằng nút Sequence.
Triển khai Code (Implementations)
Có rất nhiều thư viện và framework triển khai cây hành vi. Nhưng để hiểu rõ bản chất, chúng ta có thể tự viết một cây hành vi đơn giản từ đầu.
Đầu tiên, chúng ta định nghĩa các trạng thái của nút: Success, Failure, Running và một trạng thái Ready để chỉ nút chưa được tick:
enum Status {
Ready,
Success,
Failure,
Running,
}
Tạo một lớp trừu tượng cho các nút, có thuộc tính Status và hàm update để gọi tick và gán kết quả vào thuộc tính. Tất cả các nút sẽ kế thừa từ lớp này:
abstract class Node {
private _status = Status.Ready;
public get status() {
return this._status;
}
update() {
this._status = this.tick();
}
protected abstract tick(): Status;
}
Nút Action sẽ nhận một hàm trả về Status làm hành động:
class Action extends Node {
private action: () => Status;
constructor(action: () => Status) {
super();
this.action = action;
}
protected override tick(): Status {
return this.action();
}
}
Nút Condition nhận một hàm trả về giá trị boolean làm điều kiện:
class Condition extends Node {
private condition: () => boolean;
constructor(condition: () => boolean) {
super();
this.condition = condition;
}
protected override tick(): Status {
return this.condition() ? Status.Success : Status.Failure;
}
}
Sequence, Fallback và Parallel sẽ có một mảng các nút con, ta cần lớp Composite để quản lý các nút con này:
abstract class Composite extends Node {
protected children: Node[];
constructor(children: Node[]) {
super();
this.children = children;
}
addChild(child: Node) {
this.children.push(child);
}
}
Bây giờ ta có thể triển khai Sequence và Fallback (thực thi từng nút con theo thứ tự):
class Sequence extends Composite {
protected override tick(): Status {
for (const child of this.children) {
if (child.status === Status.Ready || child.status === Status.Running) {
child.update(); // cập nhật các nút con sẵn sàng hoặc đang chạy
}
if (child.status !== Status.Success) {
return child.status; // dừng lại khi gặp thất bại hoặc đang chạy
}
}
return Status.Success; // tất cả nút con đều thành công
}
}
class Fallback extends Composite {
protected override tick(): Status {
for (const child of this.children) {
if (child.status === Status.Ready || child.status === Status.Running) {
child.update(); // cập nhật các nút con sẵn sàng hoặc đang chạy
}
if (child.status !== Status.Failure) {
return child.status; // dừng lại khi gặp thành công hoặc đang chạy
}
}
return Status.Failure; // tất cả nút con đều thất bại
}
}
Parallel sẽ tick tất cả nút con cùng lúc và trả về Status dựa trên số lượng nút thành công:
class Parallel extends Composite {
private requiredSuccesses: number;
constructor(requiredSuccesses: number, children: Node[]) {
super(children);
this.requiredSuccesses = requiredSuccesses;
}
protected override tick(): Status {
let successCount = 0;
let runningCount = 0;
for (const child of this.children) {
if (child.status === Status.Failure) {
continue;
}
if (child.status === Status.Ready || child.status === Status.Running) {
child.update();
}
if (child.status === Status.Success) {
successCount++;
} else if (child.status === Status.Running) {
runningCount++;
}
}
if (successCount >= this.requiredSuccesses) {
return Status.Success;
}
return runningCount > 0 ? Status.Running : Status.Failure;
}
}
Decorator điều chỉnh một nút con đơn lẻ, ta tạo lớp trừu tượng cho các decorator:
abstract class Decorator extends Node {
protected child: Node;
constructor(child: Node) {
super();
this.child = child;
}
}
Ví dụ Invert sẽ đảo ngược kết quả của nút con:
class Invert extends Decorator {
protected override tick(): Status {
this.child.update();
if (this.child.status === Status.Success) {
return Status.Failure;
} else if (this.child.status === Status.Failure) {
return Status.Success;
}
return this.child.status;
}
}
Ví dụ đơn giản về robot di chuyển đến điểm A rồi tới điểm B:
const robotPosition = {x: 0, y: 0};
function atA() {
return robotPosition.x >= 10;
}
function atB() {
return robotPosition.y >= 10;
}
function moveToA() {
robotPosition.x++;
console.log("Di chuyển tới A", robotPosition.x);
return atA() ? Status.Success : Status.Running;
}
function moveToB() {
robotPosition.y++;
console.log("Di chuyển tới B", robotPosition.y);
return atB() ? Status.Success : Status.Running;
}
const behaviorTree = new Sequence([
new Fallback([
new Condition(atA),
new Action(moveToA),
]),
new Fallback([
new Condition(atB),
new Action(moveToB),
]),
]);
window.requestAnimationFrame(() => behaviorTree.update());
Ví dụ trên đơn giản hóa nhưng minh họa cách triển khai một cây hành vi từ đầu. Trong thực tế, bạn sẽ có các điều kiện và hành động phức tạp hơn nhiều.