Thông tin chung:

Ngày nhận: 18/03/2014

Ngày chấp nhận: 30/06/2014

Title:

Applying visibility-graph to the shortest path problem for robots

Từ khóa:

Đồ thị tầm nhìn, đường dẫn ngắn nhất, vật cản, hoạch định tối ưu toàn cục, Lego-Mindstorm NXT, bộ điều khiển PID

Keywords:

Visibility-graph, shortest-path, obstacles, global optimization planning, Lego-Mindstorm NXT, PID controller

ABSTRACT

This paper presents a solution for global optimized path planning with respect to finding the shortest distance for autonomous robotic system, particularly in two-dimensional space with a set of obstacles. The proposed approach is based on visibility-graph and the literature review of path planning is presented in details to explain why this approach is used. Through pros, cons, and complexity in the construction of a visibility-graph, the paper proposed two simple and efficient techniques to significantly reduce computation time in building a visibility-graph in the case of numerous obstacles. Finally, the method of how to control the robot follow exactly the identified path is shown. The experimental results, with a real robot, show that the proposed approach is efficient, feasible and straightforward to apply in practice.

TóM TắT

Bài báo trình bày giải pháp cho bài toán xác định đường đi ngắn nhất toàn cục, tránh các vật cản trong không gian hai chiều được áp dụng và kiểm thử trên robot thật. Cách tiếp cận sử dụng là dựa vào đồ thị tầm nhìn (visibility-graph). Thông qua ưu khuyết điểm và độ phức tạp trong việc xây dựng một visibility-graph, bài báo đề xuất hai phương pháp đơn giản, hiệu quả, giúp giảm đáng kể thời gian xây dựng một visibility-graph trong trường hợp môi trường chứa nhiều vật cản. Ngoài ra, bài báo cũng giới thiệu một phương pháp giúp robot di chuyển chính xác theo đường đi đã hoạch định trước. Kết quả thực nghiệm cho thấy giải pháp đề nghị này khá hiệu quả, khả thi và có thể áp dụng dễ dàng trong thực tế.