HAI CÁCH TIẾP CẬN MỚI BÀI TOÁN ĐỊNH VỊ KHOẢNG CÁCH NHỎ NHẤT
Tóm tắt: 105
| 
PDF: 48 
##plugins.themes.academic_pro.article.main##
Author
Từ khóa:
Robotics
robot localization
computational geometry
algorithm complexity
approximation algorithm
polygon triangulation
Tóm tắt
Bài toán định vị khoảng cách nhỏ nhất trong môi trường bản đồ chứa đồng dạng được đề cập. Một rô bốt được đặt tại một vị trí không biết trước trong đa giác bản đồ hai chiều P có chứa các đa giác giống nhau. Rô bốt có bản đồ P và có thể tính toán dữ liệu vùng nhìn thấy nhờ vào cảm biến. Tuy nhiên, các hình đồng dạng trong bản đồ là những dữ liệu vùng nhìn thấy giống nhau tương ứng một vài vị trí khác nhau. Mục đích là xác định đúng vị trí ban đầu trong khi rô bốt di chuyển khoảng cách nhỏ nhất. Chúng ta đề cập tới bốn thuật toán gần đúng cho vấn đề định vị rô bốt. Hai thuật toán gần đúng được giới thiệu để giải quyết bài toán định vị khoảng cách nhỏ nhất. Một trong số đó dựa vào tam giác hóa đa giác bản đồ. Và thuật toán khác sử dụng cửa sổ của vùng giao của đa giác bản đồ. Các nghiên cứu thực nghiệm trên chương trình mô phỏng được thực hiện. Các kết quả và các diễn giải được đưa ra.
Tài liệu tham khảo
-
[1] Guibas L. J., Motwani R., Raghavan P. The robot localization problem, SIAM J. Comput.1997. Vol.26. P. 1120-1138.
[2] Dudek G., Romanik K., Whitesides S., Localizing a robot with minimum travel, SIAM J. Comput.1998, Vol 27. P. 583-604.
[3] Rao M., Dudek G., Whitesides S., Randomized algorithms for minimum distance localization, Internat, J. Robotics Research, 2007, Vol 26. P. 917-934.
[4] Koenig S., Mitchell J. S. B., Mudgal A., Tovey C. A near-tight approximation algorithm for the robot localization problem, SIAM J. Comput. 2009, Vol 39. P. 461-490.
[5] Дао Зуй Нам. Сравнительный анализ алгоритмов локализации мобильного робота, использующего карту// 66-я научно-техническая конференция профессорско-преподавательского состава университета, СПБЭТУ «ЛЭТИ» 2013, Сборник докладов студентов, аспирантов и молодых ученых, 1-8 февраля 2013,г. Санкт Петербург. С. 112-115.
[6] Скворцов А.В. Построение объединения, пересечения и разности произвольных многоугольников в среднем за линейное время с помощью триангуляции, Вычислительные методы и программирование, 2002, Т. 3. С. 116-123.
[7] Seidel R. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons// Computational Geometry, Theory Application, 1991, Vol 1(1). P. 51-54.
[8] Qi M., Cao T.-T., Tan T.-S. Computing 2D Constrained Delaunay Triangulation Using Graphics Hardware, School of Computing; National University of Singapore, Technical Report # TRB3/11, March 2011. 9 с.
[9] Боресков А.В., Харламов А.А., Основы работы с технологией CUDA.- М.: ДМК-Пресс, 2010. 232.c
Xem thêm
##plugins.themes.academic_pro.article.sidebar##
Đã Xuất bản
Dec 31, 2013
Download
Cách trích dẫn
Dаo Duy Nam; S.A. Ivanovskiy. “HAI CÁCH TIẾP CẬN MỚI BÀI TOÁN ĐỊNH VỊ KHOẢNG CÁCH NHỎ NHẤT”. Tạp Chí Khoa học Và Công nghệ Đại học Đà Nẵng, vol 12, số p.h 73.1, Tháng Chạp 2013, tr 52-57, https://jst-ud.vn/jst-ud/article/view/3033.
