BỘ GIÁO DỤC VÀ ĐÀO TẠO

BỘ GIAO THÔNG VẬN TẢI

TRƯỜNG ĐẠI HỌC GIAO THÔNG VẬN TẢI TP.HCM
--------- oOo --------

BÙI QUANG VƯƠNG

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

LUẬN VĂN THẠC SĨ KỸ THUẬT

TP. HCM 10 - 2016


BỘ GIÁO DỤC VÀ ĐÀO TẠO

BỘ GIAO THÔNG VẬN TẢI

TRƯỜNG ĐẠI HỌC GIAO THÔNG VẬN TẢI TP.HCM
--------- oOo --------

BÙI QUANG VƯƠNG

ĐIỀU KHIỂN ĐỒNG BỘ
HỆ THỐNG ROBOT THÔNG MINH VẬN
CHUYỂN HÀNG TRONG KHO
CHUYÊN NGÀNH: TỰ ĐỘNG HÓA

MÃ SỐ: 605260

LUẬN VĂN THẠC SĨ KỸ THUẬT
NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. ĐẶNG XUÂN KIÊN

TP. HCM 10 - 2016


i

LỜI CẢM ƠN
Tôi xin chân thành cảm ơn quý thầy cô giảng viên Trường Đại học Giao thông
Vận tải thành phố Hồ Chí Minh đã giúp tơi trang bị kiến thức, tạo mơi trường thuận
lợi nhất trong suốt q trình học tập và thực hiện luận văn này.
Với lịng kính trọng và biết ơn, tôi xin gửi cảm ơn sâu sắc tới Tiến sĩ Đặng
Xuân Kiên đã khuyến khích, hướng dẫn, giúp đỡ tận tình cho tơi trong suốt thời gian
nghiên cứu Đề tài.
Tôi cũng xin gửi lời tri ân sâu sắc đến gia đình và những người bạn, đồng
nghiệp tại phòng Đào tạo, Viện Đào tạo Sau Đại học đã động viên, hỗ trợ tơi trong
q trình học tập, làm việc và hoàn thành luận văn này.
Theo nhận định của bản thân tác giả, với sự phát triển không ngừng của cơng
nghiệp hóa, hiện đại hóa thì ứng dụng robot vào việc vận chuyển hàng hóa trong kho
là một lĩnh vực hay và cần được nghiên cứu chuyên sâu hơn nữa. Vì thời gian và khả
năng có hạn nên luận văn khơng tránh khỏi thiếu sót và cịn nhiều vấn đề cần hồn
thiện thêm. Kính mong q Thầy Cơ và các anh chị học viên cũng như quý bạn đọc
thơng cảm. Mong rằng với những ai u thích và quan tâm đến hướng nghiên cứu
này có thể chia sẻ với tác giả để cùng nhau tiếp tục tìm hiểu, phát triển thêm nâng cao
tính ứng dụng thực tế cho đề tài.
Tác giả xin chân thành cảm ơn!



ii

LỜI CAM ĐOAN
Tơi xin cam đoan đây là cơng trình nghiên cứu của tôi.
Các số liệu, kết quả trong luận văn là thực và chưa từng được ai công bố trong bất
kỳ các cơng trình nghiên cứu nào khác.
Thành phố Hồ Chí Minh, ngày 22 tháng 10 năm 2016
Tác giả,

Bùi Quang Vương


iii

MỤC LỤC

LỜI CẢM ƠN........................................................................................................ i
LỜI CAM ĐOAN ................................................................................................. ii
MỤC LỤC ........................................................................................................... iii
DANH MỤC BẢNG..............................................................................................v
DANH MỤC HÌNH ............................................................................................ vi
1. CHƯƠNG I: TỔNG QUAN ĐỀ TÀI NGHIÊN CỨU .......................................1
1.1 Đặt vấn đề ............................................................................................... 1
1.2 Các cơng trình nghiên cứu liên quan ................................................... 1
1.2.1

Robot Kiva tại công ty Amazon .............................................. 1


1.2.2 Robot (LGV) tại kho hàng nhà máy Vinamilk Việt Nam..... 2
1.3 Những bài báo và tài liệu liên quan tới đề tài. .................................... 3
1.3.1 Những nghiên cứu ngoài nước. ............................................... 3
1.3.2 Những nghiên cứu trong nước. ............................................... 3
1.4 Mục tiêu đề tài ....................................................................................... 4
1.5 Phạm vi nghiên cứu của đề tài.............................................................. 4
1.6 Bố cục luận văn ...................................................................................... 5
2. CHƯƠNG II : CƠ SỞ LÝ THUYẾT ĐIỀU KHIỂN LIÊN QUAN .................6
2.1 Phương pháp điều khiển PID ............................................................... 6
2.1.1 Giới thiệu bộ điều khiển PID ................................................... 6
2.1.2 Rời rạc hóa bộ điều khiển PID .............................................. 10
2.2 Bài tốn tìm đường đi ngắn nhất ....................................................... 11
2.2.1 Các khái niệm về đồ thị .......................................................... 12
2.2.2 Đường đi ngắn nhất xuất phát từ một đỉnh ......................... 13
2.2.3 Đường đi trong đồ thị khơng có chu trình............................ 13
2.2.4 Thuật toán Floyd-Warshall ................................................... 15
2.2.5 Thuật toán Dijkstra ................................................................ 16
3. CHƯƠNG III: MƠ HÌNH HĨA ĐIỀU KHIỂN ĐỒNG BỘ HỆ THỐNG
ROBOT THƠNG MINH. ...................................................................................20
3.1 Mơ hình hóa của bộ điều khiển PID. ................................................. 20


iv

3.1.1
vạch
3.1.2

Thiết kế bộ điều khiển PID điều khiển robot di chuyển theo
20

Điều chỉnh tham số bộ điều khiển PID ................................. 21

3.2 Mơ hình hóa thuật tốn điều khiển robot ......................................... 28
3.2.1 Mơ hình hóa thuật tốn Dijkstra .......................................... 28
3.2.2 Chương trình bộ trung tâm điều khiển robot...................... 31
4 CHƯƠNG IV: ĐÁP ỨNG MƠ HÌNH THỰC ĐIỀU KHIỂN ĐỒNG BỘ HỆ
THỐNG ROBOT THƠNG MINH. ...................................................................52
4.1 Sơ đồ khối mơ hình cơ khí cần thi cơng ........................................... 52
4.2 Tổng quan về thiết bị phần cứng ....................................................... 53
4.2.1 Motor điều khiển .................................................................... 53
4.2.2 Vi điều khiển ........................................................................... 54
4.2.3 Các loại cảm biến .................................................................... 55
4.2.4 Nguồn cấp điều khiển ............................................................. 56
4.2.5 Sơ đồ đường vạch trong kho ................................................. 57
4.3 Mơ hình thực tế sau khi thiết kế thành công .................................... 58
4.4 Nhận xét ................................................................................................ 60
5 CHƯƠNG V: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ĐỀ TÀI .................61
5.1 Kết luận ................................................................................................ 61
5.2 Hướng phát triển đề tài ....................................................................... 61
TÀI LIỆU THAM KHẢO ..................................................................................62
PHỤ LỤC.............................................................................................................63


v

DANH MỤC BẢNG
Bảng 2-1: Kết quả tính tốn thu được khi chạy thô ............................................19
Bảng 3-1: Lựa chọn phương pháp điều chỉnh ......................................................22
Bảng 3-2: Tác động của việc tăng một thông số độc lập......................................23
Bảng 3-3: Phương pháp Ziegler–Nichols ..............................................................23

Bảng 3-4: Tính tốn thơng số bộ điều khiển .........................................................25
Bảng 3-5: Thơng số bộ điều khiển theo thực nghiệm...........................................27
Bảng 4-1: Thông số kỹ thuật của vi điều khiển ....................................................54
Bảng 4-2: Thông số kỹ thuật của cảm biến SRF05 ..............................................56


vi

DANH MỤC HÌNH
Hình 1.1. Robot Kiva tại kho hàng cơng ty Amazon .............................................2
Hình 1.2. Robot (LGV) tại cơng ty sữa Vinamilk Việt Nam .................................2
Hình 2.1. Sơ đồ hệ thống điều khiển dùng PID ......................................................6
Hình 2.2. Đồ thị PV theo thời gian, ba giá trị Kp (Ki và Kd là hằng số) .............7
Hình 2.3. Đồ thị PV theo thời gian, ứng với 3 giá trị Ki (Kp, Kd khơng đổi) .......8
Hình 2.4. Đồ thị PV theo thời gian, với 3 giá trị Kd (Kp, Ki khơng đổi) ...............9
Hình 2.5. Đồ thị sau khi chạy thơ...........................................................................19
Hình 3.1. Sơ đồ cấu trúc điều khiển ......................................................................20
Hình 3.2. Sơ đồ cấu trúc điều khiển robot ............................................................21
Hình 3.3. Xác định tham số cho mơ hình xấp xỉ bậc nhất có trễ ........................24
Hình 3.4. Mơ hình điều khiển với Kgh ...................................................................27
Hình 3.5. Quỹ đạo robot trước và sau khi hiệu chỉnh tham số bộ điều khiển ...27
Hình 3.6. Lưu đồ chương trình PID ......................................................................28
Hình 3.7. Lưu đồ thuật tốn Dijkstra ....................................................................29
Hình 3.8. Kho hàng cơng ty Vinasai tại Bình Dương...........................................31
Hình 3.9. Sơ đồ vạch đường đi của Robot trong kho ...........................................32
Hình 3.10. Hiển thị kết quả đường đi tối ưu nhất từ trạm 6 tới trạm 1 .............51
Hình 3.11. Hiển thị kết quả đường đi ngắn nhất từ trạm 1 tới trạm 5 ..............51
Hình 4.1. Sơ đồ khối của hệ thống .........................................................................52
Hình 4.2. Sơ đồ khối của robot...............................................................................52
Hình 4.3. Sơ đồ hệ thống điều khiển ......................................................................53

Hình 4.4. Động cơ điều khiển .................................................................................53
Hình 4.5. Vi điều khiển ...........................................................................................54
Hình 4.6. Cảm biến dị đường vạch .......................................................................55
Hình 4.7. Cảm biến siêu âm SRF05 .......................................................................55
Hình 4.8: Pin nguồn ................................................................................................56
Hình 4.9: Mạch ổn áp nguồn LM2596S ................................................................56
Hình 4.10. Sơ đồ đường vạch trong kho hàng ......................................................57


vii

Hình 4.11. Mặt dưới của robot thực tế ..................................................................58
Hình 4.12. Mặt trên của Robot thực tế..................................................................58
Hình 4.13. Bộ điều khiển trung tâm ......................................................................59
Hình 4.14. Robot và sơ đồ kho ...............................................................................59


1

1.

CHƯƠNG I: TỔNG QUAN ĐỀ TÀI NGHIÊN CỨU

1.1 Đặt vấn đề
Hiện nay cơng nghiệp đang từ bước hiện đại hóa, lượng sản phẩm sản xuất ra
nhiều, nên các kho hàng gia tăng từng ngày và có diện tích lớn dần. Hàng được xuất
nhập liên tục, việc sử dụng xe nâng và các băng chuyền để vận chuyển dần không
đáp ứng được nhu cầu thực tế. Đòi hỏi tất cả các công đoạn trên dây chuyền sản xuất
đều phải được tối ưu hóa đến mức cao nhất. Để tăng năng suất lao động thì cần nghiên
cứu chế tạo các robot thay thế con người ở một số công việc sản xuất. Sử dụng Robot

vận chuyển hàng hóa trong kho hàng là cách tốt nhất để đảm bảo hàng hóa được vận
chuyển thơng suốt, nhanh chóng, đảm bảo an tồn giảm thiểu tối đa cảm tính chủ
quan, robot làm việc 24/24 giờ và tối ưu được thời gian vận chuyển.
Robot có thể gom hàng từ tất cả các vị trí được lập trình sẵn, bao qt tồn bộ
nhà xưởng, điều này một cơng nhân khó có thể đảm nhiệm nếu diện tích nhà xưởng
rộng. Robot vận chuyển được khối lượng hàng hóa lớn hơn, công nhân ở cuối công
đoạn chỉ cần nhấn nút điều khiển việc cịn lại sẽ hồn tồn được tự động. Sử dụng
robot vận chuyển hàng giúp dễ dàng giám sát, quản lý, nâng cao được năng suất công
việc, giảm thiểu số lượng nhân công làm việc nặng nhọc, đưa lại lợi ích kinh tế cao
cho các doanh nghiệp.
Vì vậy, để đáp ứng nhu cầu mang tính thực tiễn cao này nên tôi đã chọn đề tài
“Điều khiển đồng bộ hệ thống robot thông minh vận chuyển hàng trong kho”.
1.2 Các cơng trình nghiên cứu liên quan
1.2.1 Robot Kiva tại công ty Amazon
Hiện nay những Robot Kiva này đã được thiết lập để hoạt động tại 10 cụm kho
hàng của Amazon tại các tiểu bang California, Texas, New Jersey, Washington và
Florida, và điều này cho phép họ cung cấp hàng triệu mặt hàng mỗi ngày cho khách
hàng. Để có thể hình dung, chúng ta cần biết chỉ riêng Amazon đã nhận được lượng
đơn đặt hàng lên đến 36,8 triệu đơn vị trên tồn cầu. Tính trung bình thì cứ mỗi giây
Amazon sẽ phải giao nhận 426 sản phẩm một lúc. Bởi vậy việc áp dụng Robot trong
một số khâu giao nhận hàng sẽ giúp Amazon tăng hiệu suất công việc lên đáng kể.


2

Hình 1.1. Robot Kiva tại kho hàng cơng ty Amazon
1.2.2 Robot (LGV) tại kho hàng nhà máy Vinamilk Việt Nam.
Tại nhà máy sữa Vinamilk các robot tự hành (LGV) điều khiển tồn bộ q
trình từ ngun liệu dùng để bao gói tới thành phẩm, giúp kiểm sốt tối ưu về chất
lượng và đảm bảo hiệu quả về chi phí.

Robot (LGV) ở đây mang hình dáng những chiếc xe tự động vận chuyển nâng,
xếp hàng. Máy móc được tích hợp thành một hệ thống và hoạt động đồng bộ, giúp
nâng hiệu quả và năng suất vượt xa so với chế độ vận hành thủ cơng.

Hình 1.2. Robot (LGV) tại cơng ty sữa Vinamilk Việt Nam


3

1.3

Những bài báo và tài liệu liên quan tới đề tài.

1.3.1 Những nghiên cứu ngồi nước.
Có nhiều nhóm nghiên cứu trên thế giới đã đạ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.
[12]
Hiện có rất nhiều công ty chuyên về sản xuất robot trên thế giới. Theo Robotic
Business Review thì trong 50 cơng ty về robot lớn nhất thế giới, hầu hết các cơng ty
này có xuất xứ từ Mỹ như iRobot, Kuka robotics, Ekso Bionics…Ngoài ra, đại diện
của châu Á có các cơng ty đến từ Nhật như Honda Robotics, Panasonic hay Foxconn
Technology group đến từ Đài Loan. Cơng ty có số lượng SC về robot nhiều nhất là
Honda với 499 SC, kế đến là Samsung: 177 SC, iRobot của Mỹ đứng thứ ba với 122
SC. [7]
Những nghiên cứu trên chưa được áp dụng rộng rãi để đưa vào thực tế vì chi
phí nghiên cứu giá thành thiết bị để sản xuất robot cao.

1.3.2 Những nghiên cứu trong nước.
Nghiên cứu robot di động đã bắt đầu rất sớm tại TP. HCM, từ ítnhất 15 năm
trước. Khoa Cơ khí, Trường Đại học Bách Khoa là một trong những đơn vị tiên phong
với cơng trình robot di động tập trung vào việc tránh vật cản. Hiện nay, trường đại
học này đã có đến 4 nghiên cứu về robot di động phục vụ công nghệ hàn, các sản
phẩm đầu ra của những nghiên cứu này bao gồm robot hàn di động hàn đứng và hàn
trần, robot di động hàn đường thẳng. Các robot này chuyển động theo đường ray hoặc
chuyển động bám theo đường hàn. Có dự án đã sản xuất ra robot di động và cung cấp
cho Xí nghiệp Đóng tàu Sài Gịn. Đại học Bách Khoa TP. HCM đang triển khai thiết
kế robot giống người tại Phịng Thí nghiệm trọng điểm. [7]


4

Ứng dụng robot di động phục vụ vệ sinh môi trường đã được hai trường đại
học kỹ thuật hàng đầu tại TP. HCM là Đại học Bách khoa và Đại học Sư phạm Kỹ
thuật thực hiện hai cơng trình vào năm 2011 về robot di động kiểm tra đường ống
thoát nước và robot làm vệ sinh ống khói. [7]
Ứng dụng trong hệ thống lưu kho và cấp phát vật tư có đề tài nghiên cứu cấp
Nhà nước tại Khu Cơng nghệ Cao TP. HCM do TS. Dương Minh Tâm chủ trì, đã
thiết kế các robot để vận chuyển linh kiện từ kho đến vị trí lắp ráp. [7]
1.4

Mục tiêu đề tài
Thiết kế, chế tạo ra 03 robot vận chuyển hàng và bộ trung tâm điều khiển,

giám sát, xử lý thu thập dữ liệu không dây cho 03 robot này. Để phục vụ cho việc vận
chuyển hàng hóa trong mơ hình kho hàng cơng ty vốn đầu tư nước ngồi.
Thiết kế bộ điều khiển cho 03 robot.
+ Điều khiển robot bám đường tự động bằng bộ điều khiển PID [2-4]

+ Kết nối không dây với trung tâm điều khiển [10-11]
Thiết kế trung tâm điều khiển, giám sát, xử lý thu thập dữ liệu khơng dây.
+ Xây dựng thuật tốn điều khiển các robot dựa vào thuật toán Dijkstra [8-9],
[12-13].
+ Thu thập dữ liệu khơng dây [10-11].
+ Thử nghiệm trên mơ hình và đánh giá giải pháp.
1.5

Phạm vi nghiên cứu của đề tài.
Đề tài nghiên cứu và thiết kế điều khiển đồng bộ hệ thống robot thơng minh

vận chuyển hàng hóa trong phạm vi mơ hình một kho hàng cụ thể.
Nghiên cứu phương thức hoạt động và xây dựng thuật tốn tìm đường đi tối
ưu cho robot.
Viết chương trình điều khiển PID để điều khiển robot bám đường vạch, cảm
biến siêu âm nhận diện và tránh vật cản, xác định vị trí robot trên đường, tối ưu thời
gian di chuyển và đồng bộ với trung tâm điều khiển.
Xây dựng thuật toán xác định hoạt động các robot, điều khiển đồng bộ các
robot dựa trên thuật toán Dijkstra.


5

Thiết kế 03 robot vận chuyển hàng giao tiếp không dây, trung tâm điều khiển.
1.6

Bố cục luận văn
Luận văn bao gồm 05 chương cụ thể như sau:
CHƯƠNG I: TỔNG QUAN ĐỀ TÀI NGHIÊN CỨU .....................................................
1.1


Đặt vấn đề .....................................................................................................

1.2

Các cơng trình nghiên cứu liên quan..........................................................

1.3

Những bài báo và tài liệu liên quan tới đề tài. ...........................................

1.4

Mục tiêu đề tài ..............................................................................................

1.5

Phạm vi nghiên cứu của đề tài. ...................................................................

1.6

Bố cục luận văn ............................................................................................

CHƯƠNG II : CƠ SỞ LÝ THUYẾT ĐIỀU KHIỂN LIÊN QUAN ................................
2.1

Phương pháp điều khiển PID ......................................................................

2.2


Bài tốn tìm đường đi ngắn nhất ................................................................

CHƯƠNG III: MƠ HÌNH HĨA ĐIỀU KHIỂN HỆ THỐNG ROBOT ........................
3.1

Mơ hình hóa của bộ điều khiển PID. ..........................................................

3.2

Mơ hình hóa thuật tốn điều khiển robot ..................................................

CHƯƠNG IV: ĐÁP ỨNG MƠ HÌNH THỰC ..................................................................
4.1

Thi cơng mơ hình cơ khí ..............................................................................

4.2

Tổng quan về thiết bị phần cứng ................................................................

4.3

Kết quả kiểm nghiệm ...................................................................................

4.4

Nhận xét chung .............................................................................................

CHƯƠNG V: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ĐỀ TÀI ..................................
5.1


Kết luận .........................................................................................................

5.2

Hướng phát triển đề tài ...............................................................................


6

2. CHƯƠNG II : CƠ SỞ LÝ THUYẾT ĐIỀU KHIỂN LIÊN QUAN
2.1

Phương pháp điều khiển PID

2.1.1 Giới thiệu bộ điều khiển PID
Bộ điều khiển PID là một bộ điều khiển vịng kín được sử dụng rộng rãi trong
cơng nghiệp. Sử dụng bộ điều khiển PID để điều chỉnh sai lệch giữa giá trị đo được
của hệ thống (process variable) với giá trị đặt (setpoint) bằng cách tính tốn và điều
chỉnh giá trị điều khiển ở ngõ ra.
Sơ đồ một hệ thống điều khiển dùng PID:

Hình 2.1. Sơ đồ hệ thống điều khiển dùng PID
Một bộ điều khiển PID gồm 3 thành phần:
P (proportional) tạo tín hiệu điều khiển tỉ lệ với sai lệch (error – e)
I (integral) tạo tín hiệu điều khiển tỉ lệ với tích phân theo thời gian của sai lệch
D (derivative) tạo tín hiệu điều khiển tỉ lệ với vi phân theo thời gian của sai
lệch
2.1.1.1 Khâu P
Khâu tỉ lệ (đơi khi cịn được gọi là độ lợi) làm thay đổi giá trị đầu ra, tỉ lệ với

giá trị sai số hiện tại. Đáp ứng tỉ lệ có thể được điều chỉnh bằng cách nhân sai số đó
với một hằng số Kp, được gọi là độ lợi tỉ lệ.
Khâu P được tính dựa trên cơng thức:
Pout = Kpe(t)
Với:

Pout: giá trị ngõ ra

(2.1)


7

KP: hằng số tỉ lệ
e: giá trị sai số (e = SP – PV)
Hàm truyền:
Gp (s) = Kp

(2.2)

Độ lợi của khâu tỉ lệ lớn là do thay đổi lớn ở đầu ra mà sai số thay đổi nhỏ.
Nếu độ lợi của khâu tỉ lệ quá cao, hệ thống sẽ không ổn định. Ngược lại, độ lợi nhỏ
là do đáp ứng đầu ra nhỏ trong khi sai số đầu vào lớn, và làm cho bộ điều khiển kém
nhạy, hoặc đáp ứng chậm. Nếu độ lợi của khâu tỉ lệ quá thấp, tác động điều khiển có
thể sẽ quá bé khi đáp ứng với các nhiễu của hệ thống.

Hình 2.2. Đồ thị PV theo thời gian, ba giá trị Kp (Ki và Kd là hằng số)
2.1.1.2 Khâu I
Phân phối của khâu tích phân (đơi khi cịn gọi là reset) tỉ lệ thuận với cả biên
độ sai số lẫn quảng thời gian xảy ra sai số. Tổng sai số tức thời theo thời gian (tích

phân sai số) cho ta tích lũy bù đã được hiệu chỉnh trước đó. Tích lũy sai số sau đó
được nhân với độ lợi tích phân và cộng với tín hiệu đầu ra của bộ điều khiển. Biên độ
phân phối của khâu tích phân trên tất cả tác động điều chỉnh được xác định bởi độ lợi
tích phân, Ki.
Khâu I được tính theo cơng thức:
t

Iout = Ki ∫0 e(t)dt
Với: Iout: giá trị ngõ ra khâu I
Ki: hệ số tích phân

(2.3)


8

e: giá trị sai số (e = SP – PV)
Hàm truyền:

G(s) =

U(s)
E(s)

=

KI
S

=


1
TI. s

(2.4)

Khâu I thường đi kèm với khâu P, hợp thành bộ điều khiển PI.
Khâu tích phân (khi cộng thêm khâu tỉ lệ) sẽ tăng tốc chuyển động của quá
trình tới điểm đặt và khử số dư sai số ổn định với một tỉ lệ chỉ phụ thuộc vào bộ điều
khiển. Tuy nhiên, vì khâu tích phân là đáp ứng của sai số tích lũy trong q khứ, nó
có thể khiến giá trị hiện tại vọt lố qua giá trị đặt (ngang qua điểm đặt và tạo ra một
độ lệch với các hướng khác). Để tìm hiểu thêm các đặc điểm của việc điều chỉnh độ
lợi tích phân và độ ổn của bộ điều khiển.

Hình 2.3. Đồ thị PV theo thời gian, ứng với 3 giá trị Ki (Kp, Kd không đổi)
2.1.1.3 Khâu D
Tốc độ thay đổi của sai số qua trình được tính tốn bằng cách xác định độ dốc
của sai số theo thời gian (tức là đạo hàm bậc một theo thời gian) và nhân tốc độ này
với độ lợi tỉ lệ Kd. Biên độ của phân phối khâu vi phân (đôi khi được gọi là tốc độ)
trên tất cả các hành vi điều khiển được giới hạn bởi độ lợi vi phân, Kd.
Khâu D được tính theo công thức:
Dout = Kd

de
dt

Với: Dout: ngõ ra khâu D
Kd: hệ số vi phân
e: giá trị sai số (e = SP – PV)


(2.5)


9

Hàm truyền:
G(s) =

U(s)
E(s)

= Kds

(2.6)

Khâu D thường đi kèm với khâu P thành bộ PD, hoặc với PI để thành bộ PID.

Hình 2.4. Đồ thị PV theo thời gian, với 3 giá trị Kd (Kp, Ki không đổi)
Khâu vi phân làm chậm tốc độ thay đổi của đầu ra bộ điều khiển và đặc tính
này là đang chú ý nhất để đạt tới điểm đặt của bộ điều khiển. Từ đó, điều khiển vi
phân được sử dụng để làm giảm biên độ vọt lố được tạo ra bởi thành phần tích phân
và tăng cường độ ổn định của bộ điều khiển hỗn hợp. Tuy nhiên, phép vi phân của
một tín hiệu sẽ khuếch đại nhiễu và do đó khâu này sẽ nhạy hơn đối với nhiễu trong
sai số, và có thể khiến q trình trở nên khơng ổn định nếu nhiễu và độ lợi vi phân đủ
lớn. Do đó một xấp xỉ của bộ vi sai với băng thông giới hạn thường được sử dụng
hơn. Chẳng hạn như mạch bù sớm pha.
2.1.1.4 Tổng hợp ba khâu của Bộ điều khiển PID
Khâu tỉ lệ, tích phân, vi phân được cộng lại với nhau để tính tốn đầu ra của
bộ điều khiển PID. Định nghĩa rằng u(t) là đầu ra của bộ điều khiển, biểu thức cuối
cùng của giải thuật PID là:

u(t) = Kpe(t) + KI∫ e(t)dt + KD
trong đó các thơng số điều chỉnh là:

de(t)
dt

(2.7)


10

Độ lợi tỉ lệ Kp giá trị càng lớn thì đáp ứng càng nhanh do đó sai số càng lớn,
bù khâu tỉ lệ càng lớn. Một giá trị độ lợi tỉ lệ quá lớn sẽ dẫn đến quá trình mất ổn định
và dao động.
Độ lợi tích phân Ki giá trị càng lớn kéo theo sai số ổn định bị khử càng nhanh.
Đổi lại là độ vọt lố càng lớn bất kỳ sai số âm nào được tích phân trong suốt đáp ứng
quá độ phải được triệt tiêu tích phân bằng sai số dương trước khi tiến tới trạng thái
ổn định.
Độ lợi vi phân Kd giá trị càng lớn càng giảm độ vọt lố, nhưng lại làm chậm
đáp ứng quá độ và có thể dẫn đến mất ổn định do khuếch đại nhiễu tín hiệu trong
phép vi phân sai số.
2.1.2 Rời rạc hóa bộ điều khiển PID
Bộ điều khiển số khơng thể lấy mẫu liên tục theo thời gian, nó cần được rời
rạc ở một vài mức. Khi cho hệ số lấy mẫu ngắn bên trong thời gian vi phân có thể đạt
được xấp xỉ một sai phân có giới hạn và tích phân qua việc lấy tổng. Chúng ta sẽ quan
tâm mỗi dạng ở một thời điểm, và sai số được tính ở mỗi khoảng lấy mẫu:
e(n) = X(n) – Y(n)

(2.8)


Bộ PID rời rạc đọc sai số, tính tốn và xuất ngõ ra điều khiển theo một khoảng
thời gian xác định (không liên tục) - thời gian lấy mẫu T. Thời gian lấy mẫu cần nhỏ
hơn đơn vị thời gian của hệ thống.
Khơng giống các thuật tốn điều khiển đơn giản khác, bộ điều khiển PID có
khả năng xuất tín hiệu ngõ ra dựa trên giá trị trước đó của sai số cũng như tốc độ thay
đổi sai số. Điều này giúp cho q trình điều khiển chính xác và ổn định hơn.
Hàm truyền của hệ thống:
u
e

(s) = H(s) = Kp(1 +

1
Ti s

+ Tds)

(2.9)

Hàm chuyển đổi:
t

1
de(t ) 
u (t )  K p  e(t )   e( )d  Td

Ti 0
dt 



Tính gần đúng theo cơng thức:

(2.10)


11

t

n

0

k 0

de(t ) e(n)  e(n  1)

t = nT
dt
T

 e( )d  T  e(k )

(2.11)

Với n là bước rời rạc tại t.
Kết quả thu được:
n

u (n)  K p e(n)  Ki  e(k )  K d (e(n)  e(n  1))

k 0

(2.12)

Với:
Ki 

2.2

K pT
Ti

Kd 

K pTd
T

Bài tốn tìm đường đi ngắn nhất
Trong lý thuyết đồ thị, bài toán đường đi ngắn nhất nguồn đơn là bài tốn tìm

một đường đi giữa hai đỉnh sao cho tổng các trọng số của các cạnh tạo nên đường đi
đó là nhỏ nhất. Định nghĩa một cách hình thức, cho trước một đồ thị có trọng số (nghĩa
là một tập đỉnh V, một tập cạnh E, và một hàm trong số có giá trị thực f : E → R),
cho trước một đỉnh v thuộc V, tìm một đường đi P từ v tới mỗi đỉnh v' thuộc V sao
cho ∑𝑝∈𝑃 𝑓 (𝑝) là nhỏ nhất trong tất cả các đường nối từ v tới v'.
Thuật toán đường đi ngắn nhất giữa mọi cặp đỉnh là một bài toán tương tự,
trong đó ta phải tìm các đường đi ngắn nhất cho mọi cặp đỉnh v và v'.
Các thuật toán quan trọng nhất giải quyết bài toán này là:
- Thuật toán Dijkstra: giải bài toán nguồn đơn nếu tất cả các trọng số đều khơng
âm. Thuật tốn này có thể tính toán tất cả các đường đi ngắn nhất từ một đỉnh xuất

phát cho trước s tới mọi đỉnh khác mà khơng làm tăng thời gian chạy.
- Thuật tốn Bellman-Ford: giải bài tốn nguồn đơn trong trường hợp trọng số
có thể có giá trị âm.
- Thuật tốn tìm kiếm A*: giải bài toán nguồn đơn sử dụng heuristics để tăng
tốc độ tìm kiếm
- Thuật tốn Floyd-Warshall: giải bài tốn đường đi ngắn nhất cho mọi cặp
đỉnh.


12

- Thuật toán Johnson: giải bài toán đường đi ngắn nhất cho mọi cặp đỉnh, có
thể nhanh hơn thuật tốn Floyd-Warshall trên các đồ thị thưa.
2.2.1 Các khái niệm về đồ thị
Trong phần này chúng ta chỉ xét đồ thị có hướng G=(V,E) và |V|=n,|E|=m với
các cung được gán trọng số, nghĩa là mỗi cung (u,v)∈ E của nó được đặt tương ứng
với một số thực a(u,v) gọi là trọng số của nó. Chúng ta sẽ đặt a(u,v)= ∞, nếu (u,v) ∉E.
Nếu dãy v0, v1 , ... , vp là một đường đi trên G, thì độ dài của nó được định nghĩa là
tổng sau:

∑pi=1 a(vi−1 , vi )

(2.13)

Tức là độ dài của đường đi chính là tổng các trọng số trên các cung của nó.
(Chú ý rằng nếu chúng ta gán trọng số cho tất cả các cung đều bằng 1, thì ta thu được
định nghĩa độ dài đuờng đi như là số cung của đường đi).
Bài tốn tìm đường đi ngắn nhất trên đồ thị dưới dạng tổng quát có thể được
phát biểu dưới dạng tổng quát như sau :
Tìm đường đi có độ dài nhỏ nhất từ một đỉnh xuất phát s∈V đến đỉnh cuối

(đích) t∈V. Đường đi như vậy sẽ gọi là đường đi ngắn nhất từ s đến t cịn độ dài của
nó sẽ kí hiệu là d(s,t) và còn gọi là khoảng cách từ s đến t (khoảng cách định nghĩa
như vậy có thể là số âm ). Nếu như không tồn tại đường đi từ s đến t thì ta đặt d(s,t)=
∞ từ đó ta thấy chu trình trong đồ thị có độ dài dương, thì trong đường đi ngắn nhất
khơng có đỉnh nào lặp lại (đường đi như thế gọi là đường đi cơ bản). Mặt khác nếu
trong đồ thị có chu trình với độ dài âm (gọi là chu trình âm) thì khoảng cách giữa 1
số cặp đỉnh nào đó của đồ thị có thể là khơng xác định, bởi vì bằng cách đi vịng theo
chu trình này một số đủ lớn lần, ta có thể chỉ ra đường đi giữa các đỉnh này có độ dài
nhỏ hơn bất kì số thực cho trước nào. Trong truờng hợp như vậy , có thể đặt vấn đề
tìm đường đi cơ bản ngắn nhất, tuy nhiên bài toán đặt ra sẽ trở nên phức tạp hơn rất
nhiều, bởi vì nó chứa bài tốn xét sự tồn tại đường đi Hamintơn trong đồ thị như là
một trường hợp riêng.
Trước hết cần chú ý rằng nếu biết khoảng cách từ s đến t, thì đường đi ngắn
nhất từ s đến t, trong trường hợp trọng số khơng âm, có thể tìm một cách dễ dàng. Để


13

tìm đường đi, chỉ cần chú ý là đối với cặp đỉnh s,t ∈ V tuỳ ý (s ≠ t) ln tìm được
đỉnh v sao cho:
d(s,t) = d(s,v) + a(v,t)

(2.14)

Thực vậy đỉnh v như vậy chính là đỉnh đi trước đỉnh t trong đường đin ngắn
nhất từ s đến t. Tiếp theo ta có thể tìm được u sao cho d(s,v)=d(s,u)+a(u,v),... Từ giả
thiết về tính khơng âm của các trọng số dễ dàng suy ra rằng dãy t,v,u... không chứa
đỉnh lặp lại và kết thúc ở đỉnh s. Rõ ràng dãy thu được xác định đường đi ngắn nhất
từ s đến t.
2.2.2 Đường đi ngắn nhất xuất phát từ một đỉnh

Phần lớn các thuật tốn tìm khoảng cách giữa hai đỉnh s và t được xây dựng
nhờ kỹ thuật tính tốn mà ta có thể mơ tả đại thể như sau: từ ma trận trọng số a(u,v),
u,v∈V, ta tính cận trên d(v) của khoảng cách từ s đến tất cả các đỉnh v∈V. Mỗi khi
phát hiện d(u)+a(u,v)d(v)=d(u)+a(u,v)

(2.15)

Q trình đó sẽ kết thúc khi nào chúng ta không làm tốt thêm được bất cứ cận
trên nào. Khi đó, rõ ràng giá trị của mỗi d(v) sẽ cho ta khoảng cách từ mỗi đỉnh s đến
v. Khi thể hiện kỹ thuật tính tốn này trên máy tính, cận trên d(v) sẽ được gọi là nhãn
của đỉnh v, cịn việc tính lại các cận trên này sẽ gọi là phép gán nhãn cho đồ thị và
toàn bộ thủ tục thường gọi là thủ tục gán nhãn. Nhận thấy rằng để tính khoảng cách
từ s đến tất cả các đỉnh còn lại của đồ thị. Hiện nay vẫn chưa biết thuật tốn nào cho
phép tìm đường đi ngắn nhất giữa hai đỉnh làm việc thực sự hiệu quả hơn những thuật
tốn tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại.
Sơ đồ tính tốn mà ta vừa mơ tả cịn chưa là xác định, bởi vì cịn phải chỉ ra
thứ tự chọn các đỉnh u và v để kiểm tra điều kiện. Thứ tự chọn này có ảnh hưởng rất
lớn đến hiệu quả thuật tốn.
2.2.3 Đường đi trong đồ thị khơng có chu trình.
Bây giờ ta xét trường hợp riêng thứ hai của bài tốn tìm đường đi ngắn nhất,
mà để giải nó có thể xây dựng thuật tốn với độ phức tạp tính tốn O(n2), đó là đồ thị


14

khơng có chu trình (cịn trọng số trên các cung có thể là các số thực tuỳ ý). Trước hết
ta chứng minh định lý sau:
Định lý 2. Giả sử G là đồ thị khơng có chu trình. Khi đó các đỉnh của nó có
thể đánh số sao cho mỗi cung của đồ thị chỉ hướng từ đỉnh có chỉ số nhỏ hơn đến

đỉnh có chỉ số lớn hơn, nghĩa là mỗi cung của nó có thể biểu diễn dưới dạng (v(i),v(j)),
trong đó iĐể chứng minh định lý ta mơ tả thuật tốn sau, cho phép tìm ra cách đánh số
thỏa mãn điều kiện định lý.
Thuật toán được xây dựng dựa trên ý tưởng rất đơn giản sau :
Trong đồ thị khơng có chu trình bao giờ cũng tìm được đỉnh có bán bậc vào
bằng 0 (khơng có cung đi vào). Bắt đầu từ đỉnh v1 nếu có cung đi vào nó từ v2 thì ta
lại chuyển sang xét đỉnh v2. Nếu có cung v3 đi vào v2, thì ta chuyển sang xét v3...
Do đồ thị là khơng có chu trình nên sau một số hữu hạn lần chuyển như vậy ta phải
đi đến đỉnh khơng có cung đi vào. Tìm các đỉnh như vậy của đồ thị, rõ ràng ta có thể
đánh số chúng theo một thứ tự tuỳ ý bắt đầu từ 1. Sau đó loại bỏ khỏi đồ thị những
đỉnh đã được đánh số cùng các cung đi ra khỏi chúng, ta thu được đồ thị mới cũng
khơng có chu trình, và thủ tục được lặp lại với đồ thị mới này. Q trình đó sẽ được
tiếp tục cho đến khi tất cả các đỉnh của đồ thị được đánh số.
Rõ ràng trong bước khởi tạo ta phải duyệt qua tất cả các cung của đồ thị khi
tính bán bậc vào của các đỉnh, vì vậy ở đó ta tốn cỡ O(m) phép tốn, trong đó m là số
cung của đồ thị . Tiếp theo mỗi lần đánh số một đỉnh, để thực hiện việc loại bỏ đỉnh
đã được đánh số cùng với các cung đi ra khỏi nó, chúng ta sẽ phải duyệt qua tất cả
các cung này. Suy ra để đánh số tất cả các đỉnh của đồ thị chúng ta sẽ phải duyệt tất
cả các cung của đồ thị một lần nữa. Vậy độ phức tạp thuật tốn la O(m).
Thuật tốn có thể để kiểm tra xem đồ thị có chứa chu trình hay khơng? Nếu
kết thúc thuật tốn vẫn cịn có đỉnh chưa được đánh số (num < n) thì điều đó có nghĩa
là đồ thị chứa chu trình.


15

Do có thuật tốn đánh số trên, nên khi xét đồ thị khơng có chu trình ta có thể
giả thiết là các đỉnh của nó được đánh số sao cho mỗi cung chỉ đi từ đỉnh có chỉ số
nhỏ đến đỉnh có chỉ số lớn hơn .

Độ phức tạp của thuật toán là O(m), do mỗi cung của đồ thị phải xét qua đúng
một lần.
Các thuật tốn mơ tả ở trên thường được ứng dụng vào việc xây dựng những
phương pháp giải bài toán điều khiển việc thực hiện những dự án lớn, gọi tắt là PERT
(Project Evaluation and Review Technique ) hqy CMD ( Critical path method)
2.2.4 Thuật toán Floyd-Warshall
Rõ ràng ta có thể giải bài tốn tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh
của đồ thị bằng cách sử dụng n lần thuật tốn mơ tả ở mục trước, trong đó ta sẽ chọn
s lần lượt là các đỉnh của đồ thị. Khi đó ta thu được thuật toán với độ phức tạp là
O(n4) (nếu dùng thuật toán Ford-Bellman) hoặc O(n3) đối với trường hợp trọng số
khơng âm hoặc đồ thị khơng có chu trình. Trong trường hợp tổng quát , sử dụng thuật
toán Ford-Bellman n lần không phải là cách làm tốt nhất . Ở đây ta sẽ mơ tả thuật
tốn với độ phức tạp tính tốn O(n3).
Thuật tốn Floyd-Warshall so sánh tất cả các đường đi có thể giữa từng cặp
đỉnh. Nó là một dạng của quy hoạch động (Dynamic Programming). Đặt hàm
adj(i,j,k) là đường đi ngắn nhất từ i đến j, chỉ dùng các đỉnh trong tập {1,2,…,k}. Giả
sử ta muốn tính adj{i,j,k+1}. Với mỗi cặp đỉnh i và j, đường đi ngắn nhất có thể là:
đường đi chỉ sử dụng các đỉnh trong tập {1,…k} hoặc đường đi từ i đến k+1 rồi từ
k+1 đến j, cũng chỉ sử dụng các đỉnh trong tập {1,…k}. Do vậy:
Trường hợp cơ bản: adj(i,j,0) = w(i,j)
Đệ quy: adj(i,j,k+1) = min{adj(i,j,k), adj(i,k+1, k) + adj(k+1, j, k)}
Code lập trình thuật tốn Floyd-Warshall
(* Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh. Đầu vào : Đồ thị cho bởi
ma trận trọng số a[i,j], i,j=1,2,...,n. Đầu ra : Ma trận đường đi ngắn nhất giữa các
cặp đỉnh d[i,j] i,j =1,2,...,n. trong đó d[i,j] cho độ dài đường di ngắn nhất từ i đến j.


16

Ma trận ghi nhận đường đi p[i,j], i, j=1,2,...,n. trong đó p[i,j] ghi nhận đỉnh đi trước

j trong đường đi ngắn nhất từ i đến j. *)
Begin (* Khởi tạo *)
For i:=1 to n do
For j:=1 to n do
Begin
d[i,j]:=a[i,j];
p[i,j]:=i;
end; (* bước lặp *)
For k:=1 to n do
For i:=1 to n do
For j:=1 to n do
If d[i,j] > d[i,k] + d[k,j] then
Begin
d[i,j]:= d[i,k] + d[k,j ];
p [i,j ]:= p [k,j ]
end;
end;
end;
2.2.5 Thuật tốn Dijkstra
Có rất nhiều thuật tốn đã được phát triển để giải bài tốn tìm đường đi ngắn
nhất giữa một cặp đỉnh, trong khuôn khổ bài viết này tôi chỉ xin giới thiệu thuật toán
Dijkstra. 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.
Dùng ma trận kề để biểu diễn đồ thị C= (cij), cij bằng trọng số của cung (i,j),
cij= +∞ nếu khơng có cung (i,j).
Một mảng d() để ghi các độ dài đường đi ngắn nhất từ s tới đỉnh i đang có.
Xuất phát d(s) =0 và d(i) = si nếu i kề s, d(j) = +∞ nếu j không kề s.