ĐIỀU KHIỂN ĐỒNG BỘ HỆ THỐNG ROBOT THÔNG MINH VẬN CHUYỂN HÀNG TRONG KHO

(1)

Bùi Quang Vương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 169(09): 229 - 232

229

ĐIỀU KHIỂN ĐỒNG BỘ HỆ THỐNG ROBOT THÔNG MINH VẬN CHUYỂN HÀNG TRONG KHO

Bùi Quang Vương¹, Đặng Xuân Kiên¹, Phạm Tâm Thành^2*

¹Trường Đại học Giao thông vận tải Tp.Hồ Chí Minh ²Trường Đại học Hàng hải Việt Nam

TÓM TẮT

Trong bài báo này, chúng tôi điều khiển đồng bộ hệ thống robot vận chuyển hàng trong kho, sử dụng thuật toán Dijkstra để tìm ra đường đi tối ưu nhất cho Robot tự hành bám đường vạch vận chuyển hàng trong kho, và thuật toán đồng bộ tránh va chạm giữa các robot. Đây là một hệ thống gồm một trung tâm điều khiển kết nối không dây với các robot tự hành bám đường vạch để điều khiển các robot vận chuyển hàng tới điểm đích xác định. Mô hình robot vận chuyển hàng đã được chế tạo thử nghiệm. Thuật toán Dijkstra, thuật toán đồng bộ được lập trình và được cài đặt trong bộ điều khiển trung tâm để điều khiển các robot. Các kết quả thực nghiệm chứng tỏ thuật toán Dijkstra cho đáp ứng tốt. Với các kết quả thu được là cơ sở để chế tạo robot vận chuyển hàng trong kho, đáp ứng yêu cầu của thực tiễn sản xuất.

Từ khóa: Mô hình robot vận chuyển, robot tự hành, thuật toán Dijkstra, tránh va, điều khiển.

ĐẶT VẤN ĐỀ^*

Robot tự hành bám đường vạch hiện nay đã được ứng dụng trong một số nhà xưởng sản xuất giúp con người vận chuyển hàng hóa tốt hơn. Nếu so sánh với những xe nâng, băng chuyền thì robot chi phí chế tạo cao hơn.

Nhưng robot lại có ưu điểm là cơ động hơn.

Tuy nhiên để nhiều robot hoạt động cùng lúc vận chuyển hàng tới các trạm đích khác nhau với thời gian nhanh nhất và quãng đường ngắn nhất là mục tiêu của hệ thống điều khiển.

Ở trong nước đã có một số công trình nghiên cứu điều khiển robot tự hành bám đường vạch, bám mục tiêu [1-5]. Trên thế giới, có nhiều nhóm nghiên cứu đã đạt được những thành tựu đáng kể về điều khiển robot di động. Trong các đối tượng robot di động thì robot tự hành cũng là một thành phần, nhóm tác giả Tae-Il Kim, Wook Bahn, Changhun Lee, Tae-jae Lee, Muhammad Muneeb Shaikh and Kwang-soo Kim của Hàn Quốc đã phát triển hệ thống tìm đường tới mục tiêu cho robot tự hành dựa trên hệ thống stereo camera, hệ thống này luôn hướng tới mục tiêu trên hệ tọa độ để tìm được đường đi tới đích [8].

Trong bài báo này, tác giả áp dụng thuật toán Dijkstra và thuật toán đồng bộ tránh va chạm vào điều khiển mô hình hệ thống robot vận

*Tel: 0904 922923, Email: phamtamthanh@vimaru.vn

chuyển hàng trong kho và đã thỏa mãn được yêu cầu đặt ra là các robot vận chuyển hàng tới trạm đích với thời gian và quãng đường tối ưu nhất.

MÔ HÌNH HỆ THỐNG ROBOT THÔNG MINH VẬN CHUYỂN HÀNG

Hình 1. Các thành phần của robot Như minh họa trên Hình 1, robot gồm có các thành phần: Động cơ và encoder các bánh, mạch điều khiển, chíp kết nối wifi, pin nguồn, mạch nguồn, cảm biến nhận vạch, cảm biến siêu âm tránh vật cản. Hệ thống gồm một bộ trung tâm điều khiển kết nối không dây với các robot tự hành bám đường vạch. Sơ đồ kho là một đồ thị mà các đỉnh của đồ thị là tọa độ điểm giao nhau hoặc tọa độ trạm giao nhận hàng.

Khi trạm giao nhận hàng A truyền tín hiệu điều xe robot lên trung tâm điều khiển thì trung tâm điều khiển sẽ tính toán và lựa chọn robot để điều đến điểm làm việc thực hiện.

(2)

230

Dựa vào thuật toán Dijkstra và thuật toán đồng bộ tránh chạm thì trung tâm sẽ điều khiển các robot di chuyển tới trạm. Sau khi nhận hàng thì robot sẽ di chuyển tới trạm đích B theo sự điều khiển của trung tâm điều khiển. Trong quá trình di chuyển của robot luôn có sự giao tiếp liên tục với trung tâm điều khiển để trung tâm giám sát, điều khiển tránh va chạm với những robot khác.

THUẬT TOÁN DIJKSTRA VÀ THUẬT TOÁN ĐỒNG BỘ TRÁNH VA CHẠM Nội dung thuật toán [6]

Thuật toán Dijkstra là một thuật toán để giải bài toán đường đi ngắn nhất nguồn đơn trên một đồ thị có trọng số cạnh mà tất cả các trọng số đều không âm. Nó xác định đường đi ngắn nhất giữa hai đỉnh cho trước, từ đỉnh a đến đỉnh b. Ở mỗi đỉnh v, thuật toán Dijkstra xác định 3 thông tin: kv, dv và pv.

kv: Mang giá trị boolean xác định trạng thái được chọn của đỉnh v. Ban đầu ta khởi tạo tất cả các đỉnh v chưa được chọn, nghĩa là kv=false,

v V

^.

dv: là chiều dài đường đi mà ta tìm thấy cho đến thời điểm đang xét từ a đến v. Khởi tạo, dv = ∞,

v V \ a , da 0

.

pv: là đỉnh trước của đỉnh v trên đường đi ngắn nhất từ a đến b. Đường đi ngắn nhất từ a đến b có dạng {a,...,pv,v,...,b}. Khởi tạo, pv = null,

v V

^.

Lưu đồ thuật toán Dijkstra Các bước của thuật toán Dijkstra

Thuật toán Dijkstra (xem minh họa trên Hình 2) gồm các bước sau [6]:

Bước 1. Khởi tạo: Đặt kv kv:=false,

v V, dv: , v V \ a , da : 0.

Bước 2. Chọn v V sao cho kv = false và dv

= min {dt / t V, kt = false} Nếu dv = ∞ thì kết thúc, không tồn tại đường đi từ a đến b.

Bước 3. Đánh dấu đỉnh v, kv:= true.

Bước 4. Nếu v = b thì kết thúc và db là độ dài đường đi ngắn nhất từ a đến b. Ngược lại nếu v ≠ b sang bước 5.

Hình 2. Lưu đồ thuật toán Dijkstra Bước 5. Với mỗi đỉnh u kề với v mà ku=false, kiểm tra Nếu du > dv + w(v,u) thì du:= dv + w(v,u). Ghi nhớ đỉnh v: pu:= v. Quay lại bước 2.

Thuật toán đồng bộ tránh va chạm

Trong mô hình thực nghiệm ta mặc định đồ thị sơ đồ kho các cạnh nối giữa hai đỉnh liền kề có trọng số bằng 1 nên khi chạy thuật toán Dijkstra sẽ trả về danh sách nhiều đường đi ngắn nhất từ trạm A đến trạm B có trọng số ngắn nhất. Kết hợp với chương trình con để đếm số lần chuyển hướng robot (quẹo trái, quẹo phải) ứng với mỗi đường đi ngắn nhất.

Đường đi ngắn nhất và có số lần chuyển hướng ít nhất sẽ được chọn là đường đi tối ưu nhất của robot từ trạm A đến điểm B.

Khi cả 3 robot cùng vận hành để tránh va chạm với nhau thì dùng thuật toán đồng bộ tránh va chạm, thuật toán này dựa trên nguyên tắc nhận diện lỗi va chạm và sửa lỗi.

Tạo bảng liệt kê ra những lỗi va chạm có thể xảy ra và phương án xử lý lỗi. Khi phát hiện lỗi va chạm chỉ cần đối chiếu bảng tra lỗi là

(3)

231 có được phương án giải quyết, thuật toán

đồng bộ tránh va chạm gồm các bước sau:

Bước 1: Khởi tạo bảng tra lỗi va chạm (loại lỗi, cách xử lý lỗi), đỉnh đầu A, đỉnh đích B.

Bước 2: Dựa vào tọa độ, chiều, hướng di chuyển của các robot để xác định có xảy ra va chạm hay không. Nếu không có va chạm thì trung tâm điều khiển gửi lệnh tới robot thực thi, chuyển sang bước 4. Nếu phát hiện lỗi có thể xẩy ra va chạm thì chuyển sang bước 3.

Bước 3: Dựa vào bảng tra lỗi va chạm sẽ xác định được giải pháp xửa lý lỗi tương ứng đưa ra. Sau đó trung tâm điều khiển gửi lệnh xuống robot thực thi.

Bước 4: Robot nhận lệnh từ trung tâm điều khiển và thực thi. Khi robot di chuyển tới đỉnh X (đỉnh kế tiếp) sẽ gửi lệnh về trung tâm điều khiển để chờ lệnh tiếp theo.

Bước 5: Trung tâm điều khiển sẽ so sánh tọa độ đỉnh X với tọa độ đỉnh đích B. Nếu trùng nhau thì đã đến đích và robot dừng lại. Nếu đỉnh X không phải là đỉnh đích B thì quay lại bước 1.

Hình 3. Ví dụ về thuật toán giải quyết xung đột giữa các robot

Ví dụ: Trường hợp lỗi như hình 3 là robot 1 đang di chuyển ở khoảng giữa từ đỉnh 20 sang đỉnh 21 thì khi đó robot 2 di chuyển từ đỉnh 13 đã đến chạm đỉnh 17 nhưng sẽ không di chuyển tiếp sang đỉnh 21 được vì đường đi từ đỉnh 17 sang đỉnh 21 bị khóa. Khi nào robot 1 đi qua đỉnh 21 tiến sang đỉnh 22 hoặc đỉnh 25 thì sẽ mở khóa đường đi giữa đỉnh 17 và đỉnh 21.

KẾT QUẢ THỰC NGHIỆM

Thuật toán Dijkastra đã giúp lập trình tìm ra được đường đi tối ưu nhất cho robot (tối ưu quãng đường và thời gian).

Thuật toán đồng bộ tránh va chạm được lập trình cài đặt sẵn trên trung tâm điều khiển đã điều khiển các robot di chuyển tới đích mà không xảy ra va chạm với những robot khác đang di chuyển.

Các robot kết nối không dây ổn định với bộ điều khiển trung tâm, quá trình truyền và nhận dữ liệu nhanh.

Kiểm nghiệm trong trường hợp cụ thể là kho hàng có sơ đồ đường vạch như hình 4.

Hình 4. Sơ đồ kho hàng giả lập

Sơ đồ kho hàng như một đồ thị các đỉnh, mỗi đỉnh được đánh dấu bằng một số, ta được ma trận sau:

{0 , 0, 0, 0, 1, 0}, {0 , 8, 9, 10, 11, 0}, {7, 12, 13, 14, 15, 2}, {0, 16, 17, 18, 19, 0}, {6, 20, 21, 22, 23, 3}, {0, 24, 25, 26, 27, 0}, {0, 5 , 0, 0, 4, 0};

Hình 5. Thiết kế 03 Robot di chuyển theo thuật toán Dijkstra, thuật toán đồng bộ tránh va chạm Sau khi sử dụng thuật toán ta tìm được đường đi ngắn nhất từ đỉnh này tới một đỉnh xác định khác.

(4)

232

Ví dụ, kết quả tìm đường đi ngắn nhất từ 6 tới 1 là chuỗi các đỉnh cần đi qua sau: 6 – 20 – 21 – 22 – 23 – 19 – 15 – 11 – 1 (Xem minh họa trên Hình 6).

Hình 6. Đường đi ngắn nhất từ 6 tới 1 Trong quá trình robot di chuyển từ đỉnh 6 tới đỉnh 1 thì thuật toán đồng bộ tránh va chạm đã giám sát, điều khiển đảm bảo không xảy ra va chạm với những robot khác.

KẾT LUẬN

Bài báo đã ứng dụng thuật toán Dijkstra, thuật toán đồng bộ tránh va chạm để đưa vào điều khiển robot vận chuyển hàng trong kho nhằm mục đích tìm đường đi ngắn nhất cho robot di chuyển tới vị trí đích, giám sát đồng bộ các robot để không xảy ra va chạm trong quá trình robot di chuyển. Qua mô hình thực tế, kết quả thu được các robot đã di chuyển tới trạm đích với đường đi tối ưu nhất, các robot di chuyển ổn định, không xảy ra va chạm. Với kết quả đạt được đã mở ra khả năng các nghiên cứu tiếp theo để xây dựng mô hình đưa vào thực tế sản xuất.

TÀI LIỆU THAM KHẢO

1. Hoàng Quang Chính, Nguyễn Thành Sơn, Nguyễn Đức Lành, Nguyễn Công Khoa (2011),

Xây dựng bộ điều khiển mờ cho Robot bám đường, Hội nghị toàn quốc về Điều khiển và Tự động hóa– VCCA-2011.

2. Nguyễn Đình Lầu, Trần Quốc Chiến, Trần Ngọc Việt (2014), Nâng cao hiệu năng tính toán cho thuật toán tìm đường đi ngắn nhất trên đồ thị mở rộng, Tạp chí Khoa học Công nghệ ĐH Đà Nẵng, Số 7(80).

3. Từ Diệp Công Thành, Phan Minh Trường, Phan Minh Thành, (2008), Điều khiển rô bốt tự hành tránh vật cản sử dụng bánh dẫn hướng Ommi, Tuyển tập hội nghị toàn quốc lần thứ 4 về Cơ điện tử, VCM 2008, tr. 356-367.

4. Ngô Mạnh Tiến, Phan Xuân Minh (2011), Nghiên cứu phát triển hệ Robot tự hành có gắn camera tự động tìm kiếm và bám mục tiêu di động, Tạp chí tự động hóa ngày nay, Số 133.

5. Võ Trung Thư, Nguyễn Anh Duy, (2008), Ứng dụng điều khiển mờ cho bài toán bám đường của rô bốt di động bằng bánh lăn, Tuyển tập hội nghị toàn quốc lần thứ 4 về Cơ điện tử, VCM 2008, tr.

305-314.

6. Dijkstra.E (1959), A note on two problems in connection with graphs, Numerische Mathematik, Vol.1.

7. Dijkstra, Edsger; Thomas J. Misa, Editor (1960). An Interview with Edsger W. Dijkstra.

Communications of the ACM 53 (8): 41–47.

8. Tae-Il Kim, Wook Bahn, Changhun Lee, Tae- jae Lee, Muhammad Muneeb Shaikh, and Kwang-soo Kim (2011), Vision System for Mobile Robots for Tracking Moving Targets, Based on Robot Motion and Stereo Vision Information, IEEE International 2011.

SUMMARY

SYNCHRONOUS CONTROL SYSTEM INTELLIGENT TRANSPORT ROBOT IN STOCK

Bui Quang Vuong¹, Dang Xuan Kien¹, Pham Tam Thanh^2*

¹Ho Chi Minh City University of Transport, ²Vietnam Maritime University (VMU) In this paper, we propose Dijkstra's algorithm to find the optimal path for Robot automatic traction transport use in the warehouse, this is a system that consists of a control center wireless connection with the robot grip to control the robot lines to determine the destination. We also present a real-time obstacle avoidance algorithm between robots. Practical model shipping robots in the warehouse was designed. Dijkstra’s algorithm was programmed and setuped in central controller to control robots.

The experimental results show the effectiveness of the proposed Dijkstra’s algorithm implementation, leading to a promising approach to aid the design shipping robots responsive.

Keywords: Model transport robot, Autonomous robot, Dijkstra's algorithm, obstacle avoidance, control

Ngày nhận bài:11/4/2017; Ngày phản biện:19/4/2017; Ngày duyệt đăng: 30/9/2017

*Tel: 0904 922923, Email: phamtamthanh@vimaru.vn