ỨNG DỤNG ĐỒ THỊ TẦM NHÌN VÀO BÀI TOÁN TÌM ĐƯỜNG CHO ROBOT

Trần Thị Như Nguyệt * , Trần Văn Hoài và Vũ Đức Lung

* Tác giả liên hệ (nguyetttn@uit.edu.vn)

Article Sidebar

Full Text: PDF

Ngày nhận bài: 18-03-2014
Ngày duyệt đăng: 30-06-2014
Ngày xuất bản: 12-10-2014
Title: Applying visibility-graph to the shortest path problem for robots
Lượt xem
58
Downloads
33
Trích dẫn
Nguyệt, T. T. N., Hoài, T. V., & Lung, V. Đ. (2014). ỨNG DỤNG ĐỒ THỊ TẦM NHÌN VÀO BÀI TOÁN TÌM ĐƯỜNG CHO ROBOT. Tạp chí Khoa học Đại học cần Thơ, (32), 42-56. Truy vấn từ https://ctujsvn.ctu.edu.vn/index.php/ctujsvn/article/view/173
Số báo
Số. 32 (2014)
Chuyên mục
Công nghệ thông tin

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.
Keywords: Visibility-graph, shortest-path, obstacles, global optimization planning, Lego-Mindstorm NXT

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ế.
Từ khóa: visibility-graph, shortest-path, obstacles, global optimization, path planning

Article Details

Tài liệu tham khảo

S. M. Valle, 2006. Planning Algorithms. Cambridge University Press. 811 pp.

S.K. Ghosh, 2007. Visibility algorithms in the plane. Cambridge University Press. 334 pp.

E. Welzl, 1985. Constructing the Visibility Graph for n Line Segments in θ(n2)Time. In:Information Processing Letters, vol. 20, issue 4: 167-171.

D. Ferguson and A.Stentz, 2006. Multi-resolution field D*. In:Proceedings of the International Conference on Intelligent Autonomous Systems (IAS).

R. Bohlin and L. Kavraki, 2000. Path planning using lazy PRM. In:IEEE Int. Conf. on Robotics and Automation, vol. 1: 521-528.

S. LaValle, 1998. Rapidly-exploring random trees: A new tool for path planning. Technical Report TR 98-11. Computer Science Dept., Iowa State University.

D. Wooden and M. Egerstedt, 2006. Oriented Visibility Graphs: Low-Complexity Planning in Real-Time Environments. In:IEEE Conference on Robotics and Automation, Orlando, FL: 2354-2359.

J. Canny, 1987. The Complexity of Robot Motion Planning Cambridge. MA: MIT Press. 196 pp.

T. Lozano-Perez, 1987. A simple motion-planning algorithm for general robot manipulators. IEEE Journal of Robotics and Automation, vol. RA-3, No. 3: 224-238.

John E. Hershberger and Subhash Suri, 1993. Efficient Computation of Euclidean Shortest Paths in the Plane, In:IEEE 34th Annual Foundations of Computer Science: 508-517.

J. O’Rourke, 1998. Computational geometry in C. Cambridge University Press. 361 pp.

J.Park and S. Oh, 2012. A New Concave Hull Algorithm and Concaveness Measure for n-dimensional Datasets. Journal of Information science and engineering, No. 100295.

X. Shen and H. Edelsbrunner, 1987. A Tight Lower Bound on the Size of Visibility Graphs. In:Inf. Process. Lett: 61-64.

J. B. Ziegler and N. B. Nichols, 1942. Optimum settings for automatic controllers. In:ASME Transactions: 759-768.

J. Kitzinger and B.Moret, 2003. The Visibility Graph Among Polygonal Obstacles: a Comparison of Algorithms. Tech. Rep. TR-CS-2003-29. University of New Mexico.