tác giả:  (1) Aya Kherrour, Khoa Kỹ thuật Thông tin và Khoa học Máy tính, Đại học Trento;  (2) Marco Robol, Khoa Kỹ thuật Thông tin và Khoa học Máy tính, Đại học Trento;  (3) Marco Roveri, Khoa Kỹ thuật Thông tin và Khoa học Máy tính, Đại học Trento;  (4) Paolo Giorgini, Khoa Kỹ thuật Thông tin và Khoa học Máy tính, Đại học Trento.  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.    Các lưới được đặc trưng bởi ba tham số: Môi trường dựa trên lưới được tạo ngẫu nhiên:  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).    Đượ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: Môi trường lưới được cá nhân hóa:  •   Đố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 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 Cấu hình chiều dài tường ngang:  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:  •   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. Chi phí đường dẫn:  •   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). Mức tiêu thụ bộ nhớ:  •   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). Thời gian giải:  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ả.  Bài viết này   theo giấy phép CC 4.0. có sẵn trên arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

EScholar Technologies

EScholar

Nghe bài viết này bằng Tiếng Anh, đọc bởi robot thông minh của HackerNoon

dài quá đọc không nổi

Make resilience your competitive advantage

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

About Author

BÌNH LUẬN

chuyên mục

BÀI VIẾT NÀY CŨNG CÓ MẶT TẠI

Related Stories

189 Stories To Learn About Reading Books

240 Stories To Learn About Astounding Stories

179 Stories To Learn About Reading

184 Stories To Learn About Psychology

189 Stories To Learn About Reading Books

240 Stories To Learn About Astounding Stories

179 Stories To Learn About Reading

184 Stories To Learn About Psychology

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps