THÁI QUỐC THẮNG
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC LẠC HỒNG
* * *
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
THÁI QUỐC THẮNG
TÌM HIỂU VÀ XÂY DỰNG PHẦN MỀM HỖ TRỢ
BÀI TOÁN TÌM ĐƢỜNG ĐI NGẮN NHẤT
TRÁNH VẬT CẢN CHO XE TỰ HÀNH
TRONG KHÔNG GIAN 2D
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC:
TS. VŨ ĐỨC LUNG
Đồng Nai - Năm 2013
LỜI CẢM ƠN
Tôi xin gởi lời cảm ơn chân thành và sâu sắc nhất đến TS. Vũ Đức Lung,
ngƣời Thầy đã tận tình hƣớng dẫn tôi trong suốt quá trình thực hiện luận văn cao
học và tạo mọi điều kiện để tôi có thể hoàn thành luận văn này.
Tôi xin gởi lời cảm ơn đến khoa Khoa Công Nghệ Thông Tin, Đại Học Lạc
Hồng; cùng Khoa Kỹ Thuật Máy Tính của Đại học Công Nghệ Thông Tin thuộc
Đại học Quốc Gia TP.HCM và Thầy cô trong khoa trong thời gian qua đã góp ý, hỗ
trợ cũng nhƣ tạo điều kiện thuận lợi cho tôi trong suốt thời gian làm luận văn.
Tôi xin cảm ơn gia đình đã động viên và tạo điều kiện tốt nhất để tôi có thể theo
đuổi việc học tập và nghiên cứu. Tôi gởi lòng tri ân đến tất cả bạn bè, những ngƣời
đã động viên, thăm hỏi cũng nhƣ đã giúp đỡ thiết thực giúp tôi hoàn tất luận văn
này
LỜI CAM ĐOAN
Tôi cam đoan: Quyển luận văn tốt nghiệp này ngoại trừ các kết quả tham khảo
từ các công trình nhƣ đã ghi rõ trong luận văn, các công việc trình bày trong luận
văn này là công trình nghiên cứu thực sự của cá nhân, đƣợc thực hiện trên cơ sở
nghiên cứu lý thuyết, kiến thức kinh điển, nghiên cứu khảo sát tình hình thực tiễn và
dƣới sự hƣớng dẫn khoa học của Tiến sĩ Vũ Đức Lung.
Một lần nữa, tôi khẳng định về sự trung thực của lời cam kết trên.
Đồng Nai, ngày 25 tháng 10 năm 2013
nhất mà không va chạm vào các vật cản một cách chính xác. Đồng thời trong mô
hình kiểm thử một camera quan sát cũng đƣợc lắp đặt trên robot, ghi nhận lại những
hình ảnh quan sát trên đƣờng đi và gởi về cho máy tính điều khiển nhằm mục đích
phục vụ cho việc xử lý thông tin và phát triển luận sau này.
MỤC LỤC
Trang
Trang phụ bìa
Lời cảm ơn
Lời cam đoan
Tóm tắt luận văn
Mục lục
Danh mục các chữ cái viết tắt
Danh mục bảng
Danh mục hình
Lời mở đầu 1
Chƣơng 1: GIỚI THIỆU ĐỀ TÀI 2
1.1. Lý do thực hiện đề tài 2
1.2. Nội dung đề tài 4
1.3. Tóm lƣợc những kết quả đạt đƣợc 4
1.4. Cấu trúc luận văn 5
Chƣơng 2: CÁC CƠ SỞ LÝ THUYẾT LIÊN QUAN 7
2.1. Tổng quát bài toán hoạch định đƣờng đi (path planning) 7
2.1.1. Giới thiệu bài toán hoạch định đƣờng đi 7
2.1.2. Các vấn đề liên quan khi giải quyết bài toán path planning 8
2.1.2.1. Không gian làm việc (Work space): 8
2.1.2.2. Không gian cấu hình (Configuration space): 8
2.1.2.3. Không gian tự do (Free space): 9
2.1.2.4. Vật di chuyển: 9
2.1.2.5. Vật cản (Obstacle): 10
4.2.1.2. Code mã giải cho bộ điều khiển P 39
4.2.1.3. Tóm tắt bộ điều khiển tỷ lệ “P” 42
4.2.2. Khâu tích phân “I” trong bộ điều khiển PID 42
4.2.2.1. Tổng thời gian chạy của error. 43
4.2.2.2. Code mã giải cho bộ điều khiển PI 44
4.2.3. Khâu vi phân “D” của bộ điều khiển PID 45
4.2.3.1. Code mã giải cho bộ điều khiển PID 47
4.2.3.2. Điều chỉnh bộ điều khiển PID 48
4.3. Kết luận: 49
Chƣơng 5: HIỆN THỰC VÀ ĐÁNH GIÁ KẾT QUẢ 50
5.1. Mục tiêu kiểm tra 50
5.2. Tổng quan thiết kế 51
5.3. Hiện thực các hoạt động của xe tự hành trên mô hình thật 53
5.3.1. Chƣơng trình tính đƣờng đi ngắn nhất của xe tự hành: 53
5.3.2. Chƣơng trình điều khiển, giao tiếp với xe tự hành 55
5.3.3. Xây dựng chức năng bám đƣờng đi chính xác cho robot Lego
Mindstorm NXT dựa trên PID: 59
5.3.4. Xây dựng chức năng xác định vị trí hiện tại của xe tự hành 61
5.3.5. Xây dựng chức năng ghi hình ảnh trên đƣờng đi của xe tự hành 63
5.4. Kết luận 64
Chƣơng 6: KẾT QUẢ ĐẠT ĐƢỢC VÀ HƢỚNG PHÁT TRIỂN 65
6.1. Kết quả đạt đƣợc 65
6.2. Hƣớng phát triển đề tài 66
TÀI LIỆU THAM KHẢO
DANH MỤC CÁC CHỮ CÁI VIẾT TẮT
AI Artificial Intelligent
CCR Concurrency and Coordination Runtime
DOF Degrees Of Freedom
DSS Decentralized Software Services
MRDS Microsoft Robotics Develop Studio
Hình 3.3. Các dạng robot thông dụng của họ Lego Mindstorm NXT 24
Hình 3.4. Các cảm biến trong bộ Lego Mindstorm NXT 25
Hình 3.5. Khả năng kết nôi với Bluetooth của Lego Mindstorm NXT 26
Hình 3.6. Môi trƣờng lập trình trên NXT-G 27
Hình 4.1. Minh họa điểm đơn giản của robot với tất cả các chi tiết cần thiết 32
Hình 4.2. Cho thấy giá trị của ánh sáng màu trắng và màu đen 34
Hình 4.3. Phân chia ánh sáng thành ba phần 34
Hình 4.4. Minh họa ba mức độ của đƣờng đi 35
Hình 4.5. Minh họa cách biến đổi trục để cân bằng giá trị error 36
Hình 5.1. Tổng quan về mô hình kiểm thử với xe tự hành 52
Hình 5.2. Giao diện mô phỏng 2D môi trƣờng chƣa vật cản 54
Hình 5.3. Ví dụ một tập tin .gw trong thƣ viện LEDA hỗ trợ tạo đồ thị 54
Hình 5.4. Hình ảnh tìm đƣờng di ngắn nhất trong chƣơng trình demo 55
Hình 5.5. Kết quả kiểm tra thực tế 59
Hình 5.6. Quỹ đạo mong muốn và tập các đƣờng đi của robot 60
Hình 5.7. Giao diện màn hình chính của chƣơng trình CSTracker6 62
Hình 5.8. Ảnh thí nghiệm với robot Mindstorm NXT đƣợc chụp từ camera 62
Hình 5.9. Giao diện chƣơng trình camera 64
1
LỜI MỞ ĐẦU
Con ngƣời thƣờng có thói quen dự định một việc gì đó trƣớc khi làm và hầu
nhƣ con ngƣời biết cần những hành động nào để đạt đƣợc những dự định đó. Để
giúp máy tính làm việc nhƣ con ngƣời, nghĩa là biết những hành động nào có thể đi
đến mục tiêu, máy tính cần đƣợc cung cấp một lƣợng tri thức. Tri thức ở đây rất đa
dạng, máy tính “hiểu” đƣợc môi trƣờng xung quanh nó nhƣ thế nào và các thao tác
cần làm là việc rất khó khăn. Một máy tính có những trang thiết bị hiện đại nhất
hiện nay vẫn chƣa thể cảm nhận hết những thay đổi của môi trƣờng. Tuy nhiên, với
sự phát triển mạnh mẽ của công nghệ thông tin những năm gần đây, máy tính đã có
thể ghi nhận những tri thức liên quan và xử lý nó trong một số bài toán cụ thể đơn
giản.
cách chính xác [22] và việc tìm kiếm đƣờng đi đó đƣợc gọi là quy hoạch đƣờng
(path planning). Nói chung, mục tiêu chính của quy hoạch đƣờng là để tìm ra một
đƣờng đi tốt nhất thỏa một số điều kiện nhƣ: khoảng cách ngắn nhất, thời gian ngắn
nhất, tiêu thụ năng lƣợng ít nhất mà một đối tƣợng có thể di chuyển dọc theo đƣờng
đi từ một điểm khởi đầu đến điểm kết thúc trong không gian hai chiều hoặc nhiều
chiều, đồng thời phải tránh đƣợc một tập hợp các vật cản. Không gian có thể là tĩnh
(các vật cản cố định và đƣợc biết trƣớc) hoặc động (các vật cản không cố định hoặc
không đƣợc biết trƣớc). Quy hoạch đƣờng chủ yếu có ba phƣơng pháp tiếp cận: dựa
trên tìm kiếm (Search-based), dựa trên lấy mẫu (Sampling-based) và tìm đƣờng tổ
hợp (Combinatorial-planning) [19]. Đặc biệt với Combinatorial-planning thì việc
tìm đƣờng đi phải thông qua việc xây dựng một tập các đƣờng có thể đi (roadmap)
và một trong những roadmap phổ biến là
visibility graph
. Việc xây dựng một tập
các đƣờng có thể đi là nhiệm vụ chính trong toàn bộ quá trình. Tuy nhiên, với một
số ứng dụng thực tế, ví dụ nhƣ: môi trƣờng có nhiều vật cản thì giai đoạn này tốn
rất nhiều thời gian. Nhiều phƣơng pháp đã đƣợc đƣa vào để giảm độ phức tạp từ
O(n
3
) xuống O(n
2
logn). Tuy nhiên, kết quả O(nlogn) chỉ là một gợi ý lý thuyết [15].
Các tác giả của phƣơng pháp này cũng khuyến cáo rằng nó là khá khó khăn để đạt
đƣợc độ chính xác O(nlogn) trong khi thực hiện, bởi vì cấu trúc dữ liệu của
O(nlogn) quá phức tạp. Mặc dù tiêu tốn nhiều thời gian nhƣng phƣơng pháp tìm các
tập đƣờng có thể đi vẫn hữu ích trong các ứng dụng tìm một đƣờng đi đến điểm
đích cho xe di chuyển tự động một cách chính xác. Phƣơng pháp này không yêu cầu
thời gian thực hoặc trong môi trƣờng tĩnh với số lƣợng vật cản trung bình, bởi vì nó
đơn giản, trực quan và có thể thực hiện đƣợc. Ngoài ra, phƣơng pháp này có thể
3
khối chức năng truyền nhận hình ảnh giữa xe tự hành và máy tính điểu khiển nhằm
phục vụ cho việc xử lý thông tin sau này.
4
1.2. Nội dung đề tài
Các nội dung chính trong đề tài gồm:
- Tìm hiểu tổng quát bài toán path planning.
- Tìm hiểu tổng quan về các giải pháp cho bài toán tìm đƣờng trên mặt
phẳng, với các đặc tính cụ thể:
+ Vật cản đa giác lồi và lõm;
+ Vật cản tĩnh không di chuyển;
+ Đối tƣợng di chuyển trong không gian có kích thƣớc (hình tròn).
- Tìm hiểu các giải thuật liên quan đến visibility graph với độ phức tạp O(n
3
)
và O(n
2
logn).
- Ứng dụng giải thuật Dijkstra để xây dựng đƣờng đi ngắn nhất.
- Tìm hiểu Bộ điều khiển PID cho robot Lego Mindstorms.
- Tìm hiểu Lego Mindstorm NXT và Microsoft Robotics Develop Studio.
- Trên những cơ sở lý thuyết đó, đề tài hoàn chỉnh các khối chức năng cần
thiết để hoàn chỉnh phần mềm có thể áp dụng vào xe tự hành thật. Các khối
chức năng cụ thể dự kiến là:
+ Xây dựng chức năng điều khiển xe tự hành di chuyển chính xác theo
đƣờng đi ngắn nhất từ phần mềm.
+ Xây dựng chức năng truyền hình ảnh trên đƣờng đi về máy tính điều
khiển.
1.3. Tóm lƣợc những kết quả đạt đƣợc
Với những nội dung và phƣơng pháp thực hiện đƣợc liệt kê trên, sau thời gian
tìm hiểu và hiện thực, đề tài sẽ đạt đƣợc các kết quả:
liệu cho máy tính hay nhận các chỉ thị từ máy tính để chạy trên sân tránh
các vật cản từ điểm đầu đến điểm đích theo đƣờng đi ngắn nhất.
1.4. Cấu trúc luận văn
Các chƣơng còn lại của luận văn bao gồm:
Chƣơng 2: Các cơ sở lý thuyết liên quan.
2.1 Tổng quát bài toán path planning.
2.2. Tổng quan các giải pháp cho bài toán path planning theo visibility
graph.
2.3. Tìm hiểu giải thuật tìm đƣờng đi ngắn nhất với độ phức tạp
O(n
2
logn).
2.4. Giải thuật Dijkstra cho một đƣờng đi ngắn nhất.
Chƣơng 3: Lego Mindstorm NXT và Microsoft Robotics Develop Studio.
3.1. Tìm hiểu Lego Mindstorm NXT.
3.2. Microsoft Robotics Develop Studio.
6
Chƣơng 4: Tìm hiểu bộ điều khiển PID cho robot Lego Mindstorms.
4.1. Giới thiệu tổng quan về Bộ điều khiển PID Controller
4.2. Các khâu chức năng trong bộ điều khiển PID
4.3. Kết luận
Chƣơng 5: Hiện thực và đánh giá kết quả
5.1. Mục tiêu kiểm tra.
5.2. Tổng quan thiết kế.
5.3. Hiện thực.
5.3.1. Môi trƣờng và đối tƣợng cụ thể đƣợc sử dụng kiểm tra.
5.3.2. Hiện thực các hoạt động của xe tự hành trên mô hình thật.
5.3.2.1. Chƣơng trình tính đƣờng đi ngắn nhất của robot.
5.3.2.2. Xây dựng khối chức năng bám đƣờng đi chính xác cho
robot Lego Mindstorm NXT dựa trên PID.
planning, tập trung vào việc giải quyết những sự không chắc chắn khi robot di
chuyển trong môi trƣờng động hay còn gọi là tìm đƣờng động cục bộ. Trong một số
tài liệu, On-line path planning cũng đƣợc nghiên cứu với tên gọi navigation
problem.
8
2.1.2. Các vấn đề liên quan khi giải quyết bài toán path planning
Giữa path planning và path mapping (bản đồ đƣờng đi) thì không nên nhằm
lẫn bởi vì path mapping tác động đến đặc tính của môi trƣờng đƣờng đi mà robot đi
qua và có thể giúp nó xác định đƣợc vị trí cần đi đến. Về mặt nghiên cứu, path
planning đƣợc phân biệt dựa trên việc tính toán đƣờng đi thông qua biểu hiện bởi
tham số thời gian. Do các robot khi di chuyển có những ảnh hƣởng động học riêng
đến từng loại robot, nên đƣờng đi (path) phải đƣợc tính toán và kết hợp với nhiều
yếu tố khác để giải quyết bài toán path planning:
2.1.2.1. Không gian làm việc (Work space):
Không gian làm việc (work space) là một mặt phẳng hai chiều gồm một
robot đƣợc xem nhƣ một điểm di động và một tập S = {P
1
,… , P
t
} của các vật
cản đa giác đƣợc đặt ở những vị trí cố định trƣớc. Việc xác định vị trí hoặc hình
dạng của robot có thể đƣợc xác định bằng vector dịch chuyển. Robot di chuyển
đƣợc thông qua một vector (x, y) bằng R(x, y). Vị trí của robot đƣợc xác định bởi
các tham số tƣơng ứng với số bậc tự do (gọi là DOF - Degrees Of Freedom) của
robot. Khi robot di chuyển trên mặt phẳng không gian 2 chiều thì có bậc là 2,
nếu số bậc tự do là 3 thì robot có thể di chuyển và quay trên mặt phẳng không
gian 3 chiều. Tham số để robot di chuyển trong không gian 3 chiều thì cao hơn.
Nhƣng do thời gian và điều kiện nên trong luận văn này chỉ đề cập đến robot di
chuyển trong mặt phẳng không gian 2 chiều.
2.1.2.2. Không gian cấu hình (Configuration space):
2.1.2.3. Không gian tự do (Free space):
Không gian dùng để thiết lập các cấu hình tránh va chạm với những vật cản
đƣợc gọi là C
free
hay còn gọi không gian tự do. Phần bù của C
free
trong C đƣợc
gọi là vật cản hoặc khu vực vùng cấm.
Thông thƣờng, khu vực vùng cắm là rất khó để tính toán một cách rõ ràng
hình dạng của C
free
. Tuy nhiên, việc thử nghiệm có đƣợc hay không thì hình
dạng đã cho trong C
free
cũng là hiệu quả. Trƣớc tiên, sự di chuyển về phía trƣớc
của robot sẽ xác định vị trí hình học của robot, và thử nghiệm sẽ cho thấy sự có
sự va chạm hay không nếu hình dạng của robot va chạm với hình dạng của môi
trƣờng.
2.1.2.4. Vật di chuyển:
Cần phải xét đến hình dạng của vật di chuyển trong bài toán đƣợc thể hiện
nhƣ thế nào khi nó di chuyển từ điểm xuất phát đến điểm đích, vì nó có ảnh
hƣởng rất lớn đến quá trình tính toán trong quá trình xây dựng một đƣờng đi tốt
nhất. Ngoài ra cũng phải xét thêm vật di chuyển có phải là chất điểm hay có kích
thƣớc hoặc có bao nhiêu bậc tự do, Trong luận văn này, vật di chuyển đƣợc
10
xem là một đối tƣợng di chuyển trong không gian có kích thƣớc (hình tròn).
2.1.2.5. Vật cản (Obstacle):
Các đa giác lồi hoặc đa giác lõm và các điểm đầu là S các điểm cuối là D
thuộc mặt phẳng R(2). Các điểm S và D không nằm trong phần lõm của đa giác
lõm nhƣ Hình (2.1). Đa giác lồi là đa giác nằm trên nữa mặt phẳng đƣợc tạo bởi
cong thì có một điểm p trên vị trí đƣờng cong của đƣờng đi đó. Nhƣ vậy, vị
trí trung tâm của đƣờng cong tập trung tại điểm p và hoàn toàn chứa trong
không gian tự do. Khi đó, một phần của đƣờng đi sẽ chứa bên trong vòng
tròn và có thể đƣợc rút ngắn bằng cách thay thế nó bằng một đoạn nối hai
điểm trên đƣờng biên của vòng tròn. Ý tƣởng này đƣợc minh họa trong
Hình 2.3.
Hình 2.3 - Một đường cong được rút ngắn bằng đường cắt [16]
Đặc điểm thứ hai, đƣờng đi chứa các đỉnh của những vật cản. Nguyên
lý này cũng tƣơng tự nhƣ đặc điểm thứ nhất. Nếu có một đỉnh v trên đƣờng
đi thì sẽ tạo ra một vòng tròn tâm tại v và hoàn toàn nằm trong không gian
tự do, đƣờng đi có thể đƣợc rút ngắn bằng cách thay thế một phần của
đƣờng đi đƣợc thực hiện lần lƣợt tại v bởi một đoạn đƣờng đi ngắn hơn. Rõ
ràng đây sẽ là trƣờng hợp, khi v là một đỉnh vật cản và ranh giới những
đƣờng biên của các vật cản. Đặc điểm này đƣợc thể hiện theo một cách
chính xác trong Bổ đề 2.1 sau đây.
Bổ đề 2.1
: Bất kỳ đường đi ngắn nhất giữa P
start
và P
goal
trong một tập
S là các vật cản đa giác rời nhau thì sẽ có một đường đi đa giác mà bên
trong là các đỉnh của S [10].
12
Để tìm đƣợc một đƣờng đi ngắn nhất, thông qua việc xây dựng từ tập
các đƣờng có thể đi (roadmap) và một trong những roadmap phổ biến là
visibility graph.
2.2. Tổng quan các giải pháp cho bài toán path planning theo visibility graph
Một đồ thị tầm nhìn, hay còn gọi là một visibility graph có hình ảnh nhƣ trong
Ký hiệu tập các vật cản là S, các nút của visibility graph là các đỉnh của S và
các cạnh của visibility graph là một cung giữa hai nút v và w nếu nó nhìn thấy
mọi đỉnh khác. Nghĩa là, nếu đoạn
hoặc là biên của vật cản hoặc là không cắt
vật cản trong S sẽ trở thành một cạnh của visibility graph. Nói cách khác, hai đỉnh
mà nhìn thấy mọi đỉnh khác thì gọi là visible, và đoạn nối chúng là một cạnh tầm
nhìn (visibility edge). Lƣu ý, hai điểm trên cùng một cạnh của đa giác thì luôn
luôn thấy mọi đỉnh khác.
Nếu bài toán thêm vào hai đỉnh P
start
và P
goal
cho mục đích xác định một
đƣờng tối ƣu nào đó giữa đỉnh này,
P
start
và P
goal
sẽ đƣợc đƣa vào tập đỉnh trong
visibility graph và các cạnh visibility edge giữa hai đỉnh này và và các đỉnh khác
cũng đƣợc thiết lập.
Để tính toán một đƣờng đi ngắn nhất từ P
start
đến P
2. Gán mỗi cung (v,w) trong G
vis
một trọng số, là chiều dài của đoạn
3. Sử dụng giải thuật Dijkstra để tính đường đi ngắn nhất giữa điểm
14
Nhƣ vậy để giải quyết bài toán path planning sử dụng visibility graph có 2 vấn
đề cần giải quyết:
(1) Tạo ra một visibility graph.
(2) Dùng giải thuật Dijkstra để tìm đƣờng đi ngắn nhất của robot trên
visibility graph đã tạo ra (có thể sử dụng các giải thuật tìm đƣờng đi ngắn
nhất trên đồ thị có trọng số khác nhƣ: Bellman-Ford, A* search, Floyd-
Warshall)
do
W
VisibleVertices
(v, S)
cho mỗi w
W, thêm vòng cung (v, w) to E
return
G
Việc xác định hai đỉnh có “nhìn thấy” (visible) với nhau hay không đƣợc
Copyright: Tài liệu đại học ©