Số liệu hiệu suất của thuật toán tìm kiếm heuristic trong môi trường lưới

3 Môi trường thử nghiệm và thước đo hiệu suất

Các thuật toán tìm kiếm heuristic đóng một vai trò quan trọng trong các lĩnh vực như tìm đường bằng robot, vì chúng xác định đường đi tối ưu cho vị trí bắt đầu và vị trí mục tiêu. Môi trường dựa trên lưới thường được sử dụng để thể hiện các kịch bản môi trường trong thế giới thực, nơi các thuật toán này có thể được triển khai, chẳng hạn như trong điều hướng tự động và robot [6]. Trong nghiên cứu này, chúng tôi phân tích toàn diện các thuật toán tìm kiếm heuristic nổi tiếng, cụ thể là D*, D* Lite, LPA*, LRTA*, RTAA* và ARA* trong các môi trường lưới khác nhau. Chúng tôi sử dụng phương pháp phỏng đoán khoảng cách Euclide để hướng dẫn tìm kiếm các thuật toán và đánh giá tác động của một số đặc điểm lưới, chẳng hạn như mật độ chướng ngại vật và kích thước lưới, đến hiệu suất của thuật toán.

Trong nghiên cứu của chúng tôi, chúng tôi sử dụng môi trường dựa trên lưới do tính đơn giản và dễ kiểm soát của chúng, ngoài việc chúng thường được sử dụng trong các nhiệm vụ lập kế hoạch đường đi trong cộng đồng nghiên cứu. Các lưới bao gồm các ô màu trắng, biểu thị các trạng thái có thể đi qua, trong khi các ô màu đen biểu thị các chướng ngại vật không thể đi qua. Tác nhân trong mô phỏng của chúng tôi có thể di chuyển theo tám hướng, với chi phí bằng 1 cho các chuyển động ngang và dọc và √ 2 cho các chuyển động chéo. Chúng tôi đã sử dụng hai loại môi trường lưới: môi trường lưới được tạo ngẫu nhiên và môi trường lưới được cá nhân hóa.

Môi trường dựa trên lưới được tạo ngẫu nhiên: Các lưới được đặc trưng bởi ba tham số:

kích thước lưới (NxN), mật độ chướng ngại vật và khoảng cách giữa trạng thái bắt đầu và trạng thái mục tiêu. Để điều tra tác động của từng tham số đến hiệu suất của thuật toán tìm kiếm, chúng tôi đã thay đổi từng tham số một cách độc lập trong khi vẫn giữ nguyên các tham số khác. Các biến thể bao gồm thay đổi kích thước lưới, thay đổi khoảng cách bắt đầu đến mục tiêu và thay đổi mật độ chướng ngại vật. Đối với mỗi lưới trong một biến thể, chúng tôi đã tạo ra mười trường hợp ngẫu nhiên có cùng tham số lưới (ví dụ: lưới có mật độ chướng ngại vật 0,25, kích thước 300x300 và 140 khoảng cách bắt đầu đến mục tiêu, có mười trường hợp được tạo ngẫu nhiên).

Môi trường lưới được cá nhân hóa: Được thiết kế để mô phỏng các tình huống cụ thể hơn. Các lưới này có kích thước cố định (71x31 đơn vị) và vị trí cố định cho cả trạng thái bắt đầu và mục tiêu, đồng thời chúng được chia thành hai phần dựa trên cấu hình chướng ngại vật của chúng:

• Cấu hình tường ngang: Đối với những thử nghiệm này, chúng tôi thêm các bức tường ngang có chiều rộng bằng một nửa lưới cho mỗi 10 đơn vị chiều dài lưới. Chúng tôi đã thêm các bức tường theo hai hướng: một lần từ trái sang phải và một lần từ phải sang trái trong lưới mới được tạo.

• Cấu hình chiều dài tường ngang: Ở đây, chúng tôi thêm tất cả các bức tường có thể có thể được đặt bên trong

chiều dài lưới và mỗi lần chúng tôi tạo một lưới mới, chúng tôi sẽ tăng tất cả chiều dài các bức tường lên 2 đơn vị.

Chúng tôi đã sử dụng hai môi trường riêng biệt này để cung cấp bản phân tích kỹ lưỡng, tìm cách tiết lộ những hiểu biết sâu sắc về hiệu suất của thuật toán tìm kiếm khi có hai tình huống cản trở khác nhau. Trong phần đầu tiên, các chướng ngại vật nằm rải rác ngẫu nhiên trong lưới, trong khi ở phần thứ hai, các cấu trúc giống như bức tường, xuất hiện dưới dạng một khối các chướng ngại vật được kết nối với nhau.

Để đánh giá hiệu suất của các thuật toán tìm kiếm khác nhau được sử dụng trong thử nghiệm, chúng tôi đã chọn các số liệu sau:

• Chi phí đường dẫn: Số liệu đo độ dài đường dẫn hoặc số lượng hành động được thực hiện từ đầu đến trạng thái mục tiêu. Nó cho thấy chất lượng của giải pháp.

• Mức tiêu thụ bộ nhớ: Nó đo lượng bộ nhớ cần thiết để thuật toán tìm ra giải pháp. Việc kiểm tra khả năng mở rộng của thuật toán là cần thiết và nó được đo bằng (KB).

• Thời gian giải: Biểu thị tổng thời gian mà một thuật toán cần để tìm lời giải tính bằng (ms), tính bằng mili giây (ms).

Chúng tôi đã thực hiện thử nghiệm của mình trên lõi Intel i9 27 GHz, được trang bị RAM 250Gb và chạy Ubuntu Linux 22.04. Sử dụng các cài đặt sau: Tất cả các thuật toán đều sử dụng khoảng cách Euclide làm hàm heuristic. Đối với LRTA* và RTAA*, chúng tôi đặt số lượng nút đã sử dụng thành 250 cho mỗi lần lặp. Thuật toán ARA* được chạy với trọng số 2,5 cho phương pháp heuristic. Chúng tôi đã chạy mỗi thuật toán 100 lần trên mỗi lưới để tính ngẫu nhiên và đảm bảo độ tin cậy của kết quả.