TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI HANOI UNIVERSITY OF INDUSTRY Tập san SINH VIÊN NGHIÊN CỨU KHOA HỌC Số 14 ● 2024 195
NGHIÊN CỨU XÂY DỰNG BẢN ĐỒ TỰ ĐỘNG
TRÊN ROBOT DI ĐỘNG KIỂU VI SAI
RESEARCH ON AUTOMATIC MAP CONSTRUCTION
ON A DIFFERENTIAL MOBILE ROBOT
Đào Thanh Sơn1,*, Hoàng Công Chất1, Tạ Xuân Sơn1,
Lê Đức Thắng1, Lê Văn Nghĩa2
1Lớp CODT 03 - K15, Trường Cơ khí - Ô tô, Trường Đại học Công nghiệp Hà Nội
2Trường Cơ khí - Ô tô, Trường Đại học Công nghiệp Hà Nội
*Email: daothanhsonn076@gmail.com
TÓM TẮT
Để robot di động có thể di chuyển một cách hiệu quả, việc biết trước bản đồ là điều cần thiết. Vấn đề lập bản đồ thông
thường sẽ được thực hiện thủ công. Điều này dẫn tới những hạn chế như tiêu tốn thời gian, nhân lực, bị giới hạn bởi phạm
vi của bộ điều khiển hoặc các môi trường độc hại mà con người không thể tiếp cận. Bài viết này trình bày một chiến lược
khám phá tự động cho robot di động dựa trên việc sử dụng thuật toán RRT. Đặc tính của thuật toán là việc tạo ra một cây
ngẫu nhiên và luôn có xu hướng mở rộng về các vùng không gian chưa xác định. Điều này cho phép robot xác định được
các điểm biên giới để hướng tới khám phá hiệu quả môi trường. Chiến lược đề xuất được triển khai và thử nghiệm trên hệ
điều hành robot ROS áp dụng với mô hình robot di động kiểu vi sai. Các kết quả mô phỏng và thực nghiệm cho thấy robot
đã thành công trong việc lập bản đồ tự động với chất lượng bản đồ đầu ra tốt.
Từ khóa: Lập bản đồ; ROS; RRT
ABSTRACT
For mobile robots to move effectively, knowing the map in advance is essential. Mapping is currently normally done
manually. This leads to limitations such as consuming time, manpower, being limited by the controller's range or toxic
environments that humans cannot access. This paper presents an automatic discovery strategy for mobile robots based on
the use of the RRT algorithm. The characteristic of the algorithm is the creation of a random tree and always tends to
expand into unknown spatial regions. This allows the robot to identify boundary points towards efficient exploration of
the environment. The proposed strategy is implemented and tested on the robot operating system ROS applied to a
differential-type mobile robot model. Simulation and experimental results show that the robot is successful in automatic
mapping with good output map quality.
Keywords: Mapping; ROS; RRT
CHỮ VIẾT TẮT
RRT Rapidly exploring Random Tree (Cây ngẫu nhiên khám phá nhanh)
ROS Robot Operating System (Hệ điều hành robot)
SLAM Simultaneous Localization And Mapping (Định vị và lập bản đồ đồng thời)
1. GIỚI THIỆU
Mục tiêu chính của các thuật toán khám phá robot tự trị
là dẫn dắt robot vào các khu vực chưa biết, qua đó mở rộng
phần đã biết của bản đồ được tạo ra khi robot di chuyển.
Các chiến lược thăm dò dựa trên biên giới [1 - 6] thường
được sử dụng trong quá trình này, khi robot tiến đến các vị
trí nằm trên rìa của khu vực đã khám phá. Các cạnh biên
giới được xác định là những đường ranh giới ngăn cách
không gian đã biết với không gian chưa biết trong bản đồ
lưới chiếm dụng. Khi một cạnh biên giới được phát hiện,
một điểm trên cạnh, thường là trung tâm, sẽ được robot gán
để thực hiện thăm dò. Quá trình trích xuất các cạnh biên
giới yêu cầu xử lý toàn bộ bản đồ, và khi bản đồ mở rộng,
việc xử lý này sẽ tiêu tốn nhiều tài nguyên tính toán hơn [7].
Điều này dẫn đến nghiên cứu về phương pháp phát hiện
biên giới hiệu quả [7, 8].
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI HANOI UNIVERSITY OF INDUSTRY Tập san SINH VIÊN NGHIÊN CỨU KHOA HỌC Số 14 ● 2024 196Chiến lược dựa trên biên giới lần đầu tiên được giới
thiệu bởi Yamauchi [1]. Chiến lược thăm dò được sử dụng
là xác định tất cả các khu vực biên giới trong bản đồ hiện
tại và sau đó lái robot đến điểm biên giới gần nhất. Phương
pháp này có hai thiếu sót cho nhiệm vụ thăm dò. Đầu tiên,
nó đối xử với tất cả các biên giới như nhau. Thứ hai, nó
được giới hạn trong một nguồn thông tin: tìm kiếm địa hình
mới. Vì vậy, nhiều thuật toán lựa chọn điểm biên giới khác
nhau được đề xuất. Simmons [9] và Moorehead [10] trình
bày chức năng lựa chọn điểm biên giới bằng cách kết hợp
thu thập thông tin và chi phí thăm dò để chọn điểm biên giới
mục tiêu. Carlone [11] sử dụng mô hình lập trình tuyến tính
số nguyên hỗn hợp để có được điểm biên giới tối ưu cho
thăm dò tự trị. Công trình của Mei [12] đề xuất một thuật
toán để chọn điểm biên giới mục tiêu tiếp theo để robot
khám phá dựa trên thông tin định hướng. Nhóm nghiên cứu
của trường đại học Laguna và đại học Bonn [13] đề xuất
một chiến lược thăm dò mới khai thác kiến thức nền tảng
bằng cách xem xét các môi trường đã thấy trước đó để đưa
ra quyết định thăm dò tốt hơn. Gautam [14] sử dụng thuật
toán K-means để nhóm các điểm biên giới và gán các điểm
biên giới này cho robot bằng phương pháp Hungary.
Bài viết này trình bày một chiến lược để phát hiện các
điểm biên giới bằng cách sử dụng thuật toán RRT [15]. Các
điểm biên giới được phát hiện sẽ được lọc và đưa vào hàng
đợi để gán cho robot. Khi một điểm được gán, robot sẽ di
chuyển đến điểm đó và sử dụng cảm biến lidar để quét và
khám phá các khu vực lân cận trong phạm vi cảm biến.
Chiến lược thăm dò này được triển khai trên một robot duy
nhất sử dụng khung ROS. Các kết quả mô phỏng và thực
nghiệm cho thấy robot đã thành công trong việc khám phá
tự động khu vực được chỉ định với chất lượng bản đồ đầu
ra tốt.
2. MÔ HÌNH ĐỘNG HỌC ROBOT DI ĐỘNG KIỂU VI
SAI
Hình 1. Mô hình robot di động kiểu vi sai
Đối tượng hướng tới trong bài viết là một robot di động
vi sai với hai bánh dẫn động độc lập (hình 1). Trong quá
trình xây dựng mô hình động học và thiết lập các trạng thái
chuyển động cho robot đưa ra các giả định bánh xe lăn
không trượt và robot chuyển động trong mặt phẳng
Oxy
.
Vectơ tư thế
p
và vectơ vận tốc
p
của robot được cho bởi:
T
Q Q
T
Q Q
x y
x y
p
p
(1)
Trong đó
Q
và
Q
y
là tọa độ xác định vị trí của robot
trong hệ tọa độ
Oxy
,
là góc quay của robot.
Từ hình 1, chúng ta có vận tốc tuyến tính của bánh xe
bên phải
r
v
và vận tốc tuyến tính của bánh xe bên trái
l
v
:
r r Q
l l Q
v r v a
v r v a
(2)
Trong đó
r
,
2
a
lần lượt là bán kính và khoảng cách
giữa hai bánh xe chủ động;
Q
v
là vận tốc tuyến tính của
robot;
l
,
r
lần lượt là vận tốc góc của bánh xe bên trái
và bên phải.
Từ hình 1 và phương trình (2) ta có mô hình động học
của robot được mô tả bởi:
cos cos
2 2
sin sin
2 2
2 2
Q
r
Q
l
r r
xr r
y
r r
a a
p Jq
(3)
Trong đó
J
là ma trận Jacobian của robot,
q
là vectơ
vận tốc góc của bánh xe. Từ phương trình (3) ta có phương
trình động học nghịch đảo:
1
T T
*
q J p J J J p
cos sin
1
cos sin
Q
r
Q
l
x
a
y
a
r
(4)
Trong đó
*
J
là nghịch đảo tổng quát của
J
.
3. CHIẾN LƯỢC KHÁM PHÁ BẢN ĐỒ TỰ ĐỘNG
Bài báo này trình bày một chiến lược thăm dò dựa trên
việc sử dụng thuật toán cây ngẫu nhiên khám phá nhanh
RRT. Thuật toán RRT được chọn vì nó có đặc tính mở rộng
một cây thiên về các vùng chưa được khám phá.
Trong mỗi lần lặp, một nút
rand
q
được tạo ra ngẫu nhiên
trong không gian trạng thái và nút
nearest
q gần nhất tới nút
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI HANOI UNIVERSITY OF INDUSTRY Tập san SINH VIÊN NGHIÊN CỨU KHOA HỌC Số 14 ● 2024 197rand
q trong cây hiện tại được tìm kiếm. Theo hướng từ nút
nearest
q đến nút rand
q, một ứng cử viên cho một nút mới là
new
q được tính toán ở một khoảng cách được xác định trước
tối đa là
. Nếu nút new
q và kết nối từ nút nearest
q đến nút
new
q nằm trong vùng không gian trống thì nút new
q được
chọn làm nút mới và kết nối của nó với nearest
q được thêm
vào cây. Quá trình này được lặp đi lặp lại cho tới khi đạt
điều kiện kết thúc. Cuối cùng ta thu được một cây phát triển
rộng khắp trong toàn bộ không gian từ một nút init
q khởi
tạo ban đầu. Quá trình của thuật toán được minh họa trong
hình 2 và 3.
Hình 2. Minh họa thuật toán RRT
Hình 3. Quá trình mở rộng cây của thuật toán RRT [16]
Dựa trên đặc tính mở rổng của thuật toán RRT, ta xác
định được các điểm biên giới là điểm giao giữa RRT với
ranh giới giữa hai khu vực đã biết và chưa biết. Bằng việc
hướng robot tới các điểm biên giới này giúp robot có thể
động khám phá được bản đồ. Quá trình tìm kiếm các điểm
biên giới được minh họa tại hình 4.
Hình 4. Quá trình tìm kiếm các điểm biên giới
Sơ đồ tổng thể của quá trình khám phá tự động được thể
hiện tại hình 5. Đầu tiên nút RRT boundary point detector
sẽ phát hiện các điểm biên giới trên bản đồ như mô tả tại
hình 4. Các điểm biên được tìm thấy được gửi tới nút bộ lọc
Filter. Nút bộ lọc này nhận các điểm biên được phát hiện,
lọc bỏ các điểm biên đã cũ khi bản đồ được mở rộng trong
quá trình robot di chuyển và chuyển chúng đến nút Assigner
để chỉ huy robot. Nút Assigner nhận các mục tiêu khám phá
là các điểm biên đã được lọc do nút Filter công bố và ra lệnh
cho robot di chuyển đến vị trí điểm biên có khoảng cách tốt
nhất tới robot. Trong quá trình robot di chuyển bản đồ cũng
như vị trí của robot sẽ được cập nhật thông qua một kỹ thuật
SLAM là Gmapping [17, 18].
Hình 5. Sơ đồ quá trình khám phá và lập bản đồ tự động của robot
4. KẾT QUẢ VÀ THẢO LUẬN
Hình 6. Quá trình khám phá và lập bản đồ trong mô trường mô
phỏng
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI HANOI UNIVERSITY OF INDUSTRY Tập san SINH VIÊN NGHIÊN CỨU KHOA HỌC Số 14 ● 2024 198Quá trình mô phỏng và thực nghiệm hệ thống đều được
triển khai trên nền ROS. Sau khi xác định vùng không gian
mà robot cần khám phá, quá trình lập bản đồ sẽ tự động diễn
ra. Cây RRT sẽ phát triển và tìm ra các điểm biên giới.
Robot di chuyển đến các điểm biên giới được chọn để thực
hiện việc thăm dò. Các kết quả tại hình 6 và 7 cho thấy khu
vực chỉ định được robot khám phá đầy đủ trong cả môi
trường mô phỏng và thực nghiệm. Chất lượng bản đồ đầu
ra tốt thể hiện tại hình 8.
Hình 7. Quá trình khám phá và lập bản đồ trong mô trường thực
nghiệm
a) Môi trường mô phỏng b) Môi trường thực nghiệm
Hình 8. Bản đồ thu được sau quá trình khám phá trong môi
trường mô phỏng và thực nghiệm
Hình 9. Biểu đồ vận tốc dài của robot trong quá trình mô phỏng
Hình 10. Biểu đồ vận tốc dài của robot trong quá trình thực
nghiệm
Hình 11. Biểu đồ vận tốc góc của robot trong quá trình mô phỏng
Hình 12. Biểu đồ vận tốc góc của robot trong quá trình thực
nghiệm
Từ các biểu đồ vận tốc thể hiện từ hình 9 đến hình 12, ta
thấy với cùng một kiểu khu vực khám phá là không có vật
cản, robot thực hiện di chuyển quay theo vòng tròn để khám
phá được hoàn toàn khu vực đó. Đối với môi trường mô
phỏng robot quay ngược chiều kim đồng hồ, trong môi
trường thực nghiệm robot quay cùng chiều kim đồng hồ.
Các biểu đồ vận tốc của robot trong môi trường mô phỏng
mịn hơn so với thực nghiệm. Điều này là do robot thực
nghiệm chịu ảnh hưởng từ nhiễu cảm biến cũng như môi
trường xung quanh.
5. KẾT LUẬN VÀ KIẾN NGHỊ
Bài báo này trình bày một chiến lược giúp robot có thể
tự động khám phá được bản đồ mà không cần tới sự hướng
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI HANOI UNIVERSITY OF INDUSTRY Tập san SINH VIÊN NGHIÊN CỨU KHOA HỌC Số 14 ● 2024 199dẫn của con người. Dựa trên thuật toán RRT, các điểm biên
giới trong không gian được tìm thấy một cách hiệu quả,
robot di chuyển tới các điểm biên này và thực hiện mở rộng
bản đồ thông qua một thuật toán SLAM. Các kết quả mô
phỏng và thực nghiệm cho thấy chiến lược đưa ra là hiệu
quả, khu vực yêu cầu khám phá được lập bản đồ một cách
hoàn thiện với chất lượng cao.
Tuy robot đã thành công trong việc tự khám phá và lập
bản đồ trong một không gian trống nhưng vẫn còn nhiều
hạn chế khi khó có thể lập được bản đồ trong môi trường có
vật cản hoặc phức tạp hơn do vẫn chưa xem xét đến các vấn
đề liên quan đến việc hoạch định đường đi và điều hướng.
Các công việc trong tương lai sẽ được tiến hành để giải
quyết các vấn đề này.
TÀI LIỆU THAM KHẢO
[1]. Yamauchi, B., 1997. A frontier-based approach for autonomous exploration. Proceedings 1997 IEEE
International Symposium on Computational Intelligence in Robotics and Automation CIRA'97.'Towards New
Computational Principles for Robotics and Automation'. 146-151.
[2]. Yamauchi, B., 1998. Frontier-based exploration using multiple robots. Proceedings of the second international
conference on Autonomous agents. 47-53.
[3]. Wang, Y., Liang, A., & Guan, H., 2011. Frontier-based multi-robot map exploration using particle swarm
optimization. IEEE symposium on Swarm intelligence. 1-6.
[4]. Senarathne, P. G. C. N., & Wang, D., 2015. Incremental algorithms for Safe and Reachable Frontier Detection
for robot exploration. Robotics and Autonomous System. 72, 189-206.
[5]. Keidar, M., & Kaminka, G. A., 2014. Efficient frontier detection for robot exploration. The International Journal
of Robotics Research. 33(2), 215-236.
[6]. Umari, H., & Mukhopadhyay, S., 2017. Autonomous robotic exploration based on multiple rapidly-exploring
randomized trees. International Conference on Intelligent Robots and Systems. 1396-1402.
[7]. Senarathne, P. G. C. N., Wang, D., Wang, Z., & Chen, Q., 2013. Efficient frontier detection and management for
robot exploration. International Conference on Cyber Technology in Automation, Control and Intelligent Systems. 114-
119.
[8]. Keidar, M., & Kaminka, G. A., 2012. Robot exploration with fast frontier detection: Theory and experiments.
Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 1. 113-120.
[9]. R. G. Simmons, D. Apfelbaum, W. Burgard, D. Fox, M. Moors, and S. Thrun, 2000. Coordination for Multi-
Robot Exploration and Mapping. Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on
Innovative Applications of Artificial Intelligence. 852–858.
[10]. Moorehead, S. J., Simmons, R., & Whittaker, W. L., 2001. Autonomous exploration using multiple sources of
information. Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation. 3098-3103.
[11]. Carlone, L., & Lyons, D., 2014. Uncertainty-constrained robot exploration: A mixed-integer linear programming
approach. International Conference on Robotics and Automation. 1140-1147.
[12]. Mei, Y., Lu, Y. H., Lee, C. G., & Hu, Y. C., 2006. Energy-efficient mobile robot exploration. Proceedings 2006
IEEE International Conference on Robotics and Automation. 505-511.
[13]. Ström, D. P., Bogoslavskyi, I., & Stachniss, C., 2017. Robust exploration and homing for autonomous robots.
Robotics and Autonomous Systems. 90, 125-135.
[14]. Gautam, A., Murthy, J. K., Kumar, G., Ram, S. A., Jha, B., & Mohan, S., 2015. Cluster, allocate, cover: An
efficient approach for multi-robot coverage. International Conference on Systems, Man, and Cybernetics. 197-203.
[15]. LaValle, S., 1998. Rapidly-exploring random trees: A new tool for path planning. Research Report 9811.
[16]. Klancar, G., Zdesar, A., Blazic, S., & Skrjanc, I., 2017. Wheeled mobile robotics: from fundamentals towards
autonomous systems. Butterworth-Heinemann.
[17]. Grisetti, G., Stachniss, C., & Burgard, W., 2005. Improving grid-based slam with rao-blackwellized particle filters
by adaptive proposals and selective resampling. Proceedings of the 2005 IEEE international conference on robotics and
automation. 2432-2437.
[18]. Grisetti, G., Stachniss, C., & Burgard, W., 2007. Improved techniques for grid mapping with rao-blackwellized
particle filters. IEEE transactions on Robotics. 23(1), 34-46.