nguyentrungtien112
New Member
Download Luận văn Một số phương pháp chính xác lập lộ trình chuyển động cho robot
Mục lục
CHươNG I: GIơI THIệU BàI TOáN Lậ P TRìNH CHO ROBOT . 7
1.1. Robot nhân tạo . 7
1.2. Bài toán lập lộ trình . 9
1.3.Ví dụ và những ứng dụng về lộ trình Robot . 12
1.4. Những thành phần cơ bản của việc lập lộ trình . 16
1.5. Giải thuật, ng ười lập lộ trình và lộ trình . 17
1.6. Kết luận . 23
Chương IIư cấu hình không gian trạng thái . 24
2.1.Các Khái niệm cấu hình không gian . 24
2.1.1. Chướng ngại (Obstacle) . 24
2.1.2. Không gian trống ( Free Spaceư Cfree) . . 25
2.2. Mô hình cấu hình . 26
2.2.1. Mô hình hình học . 26
2.2.2. Mô hình nửa Đại số . 32
2.3. Các phép biến đổi của robot . 35
2.4. Không gian cấu hình ch ướng ngại vật . 37
2.5ư Định nghĩa chính xác về vấn đề lập lộ trình chuyển động . 38
2.6. Một số mô hình Cobs. 39
2.7. Kết luận . 47
Chương IIIưMột số phương pháp chính xác lập lộ trình chuyển Động . 48
3.1.Giới thiệu chung . 48
3.2. Biểu diễn không gian chướng ngại vật . 50
3.3. Một số giải thuật lập lộ trình chính xác cho robot . 53
3.3.1 . Roadmap Visibility Graph – Đồ thị tầm nhìn . 53
3.3.2. Vertical Cell Decomposition ( phân ly Ô dọc ) . 59
Kết luận . 68
Tài liệu tham khảo. 69
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
ở đây một logic vị từ đã đ•ợc định nghĩa nh• sau: : W {TRUE, FALE}.
Hàm trả lại giá trị TRUE khi một điểm trong W nằm bên trong O, và ng•ợc lại là
False . Cho một đ•ờng thẳng f(x, y ) = 0 để e(x, y) biểu thị một vị từ lôgíc trả lại
giá trị TRUE nếu f(x, y) = 0, và ng•ợc lại là FALSE. Một vị từ t•ơng ứng tới một
vùng đa giá c lồi đ•ợc biểu diễn bởi các phép hội nh• sau:
Vị từ (x, y) trả về giá trị TRUE nếu điểm (x, y) nằm trong vùng đa giá c lồi,
ng•ợc lại là FALSE. Một vùng ch•ớng ngại mà gồm có n đa giác lồi đ•ợc biểu diển
bởi tuyển nh• sau:
(2.5)
(2.6)
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
30
Mặc dầu tồn tại những ph•ơng pháp hiệu quả hơn, có thể kiểm tra một điểm
( x, y) nằm trong O với thời gian O(n), trong đó n là số mẫu mà xuất hiện trong biểu
diễn của O ( Mỗi mẫu đ•ợc •ớc l•ợng trong hằng số thời gian). Bất kỳ mệnh đề
lôgíc phức tạp đến đâu đều có thể đ•ợc tách nhỏ thành những chuẩn tuyển ( Đây th-
ường được gọi “ tổng của những tích ” trong khoa học máy tính). Như vậy chúng ta
có thể nói bất kỳ một không gian O luôn luôn đ•ợc biểu diễn bằng hợp của hữu hạn
các phép giao những mẫu.
2.2.1.2- Mô hình đa diện:
Trong không gian ba chiều W = R3 , những khái niệm có thể đ•ợc khái quát
hóa rất tốt từ tr•ờng hợp không gian 2D bởi việc thay thế đa giác bằng khối đa d iện
và thay thế nửa mặt phẳng bởi nửa không gian mẫu.
Một ranh giới biểu diễn có thể đ•ợc định nghĩa d•ới dạng ba đặc tr•ng : đỉnh,
cạnh, và mặt. Một vài cấu trúc dữ liệu đ•ợc đ•a ra để biểu diễn đa diện, ví dụ, cấu
trúc dữ liệu chứa ba kiểu bản ghi : đỉnh, mặt và nửa cạnh (một nửa cạnh là cạnh có
h•ớng).
Giả sử O là một đa diện lồi, nh• trong Hình 2.5. Một biểu diễn ba chiều có
thể đ•ợc xây dựng từ những đỉnh. Mỗi mặt của O có ít nhất ba đỉnh dọc theo ranh
giới của nó. Giả thiết rằng những đỉnh này không cộng tuyến, một ph•ơng trình của
mặt phẳng đi qua chúng có dạng:
ax + by + cz + d = 0 (2.7)
trong đó a, b, c, d R là những hằng số.
Một lần nữa, f có thể xây dựng bằng ánh xạ f : R3 R và
f(x, y, z) = ax + by + cz + d. (2.8)
với m mặt. Cho mỗi mặt của O, một nửa - không gian Hi đ•ợc định nghĩa nh• một
tập con của W:
(2.9)
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
31
Điều quan trọng là chọn fi để nó giữ những giá trị âm ở trong đa diện. Trong
mô hình đa giác, để thích hợp với định nghĩa f i là việc xuất phát đi vòng quanh biên
theo thứ tự ng•ợc chiều kim đồng hồ. Trong tr•ờng hợp một đa diện, ranh giới của
mỗi mặt là các cạnh cũng đ•ợc lấy ng•ợc chiều kim đồng hồ. (Hình 2.6b)
Ph•ơng trình cho mỗi mặt đ•ợc xác định nh• sau: Chọn ba đỉnh liên tiếp p1,
p2, p3 (không đ•ợc cộng tuyến ) theo thứ tự ng•ợc chiều kim đồng hồ. Cho v 12 biểu
thị vectơ từ p1 tới p2, v23 biểu thị vectơ từ p2 đến p3. Tích v = v12 x v23 luôn luôn là
một vectơ nằm trong mặt phẳng gọi là vectơ hồi. Véc tơ [a b c] song song với mặt
phẳng. Nếu những thành phần của nó đ•ợc chọn là a = v[1], b=v[2], c = v[3], thì
f(x, y, z) = 0 cho mọi điểm trong nửa - không gian chứa đa diện.
Hình 2.6: (a) Mô tả một đa diện d•ới dạng mặt, cạnh, và đỉnh. ( b) Những cạnh
của mỗi mặt có thể đ•ợc l•u trữ trong chu trình theo thứ tự ng•ợc chiều kim đồng
hồ.
Trong tr•ờng hợp của một đa giác mẫu, một đa diện lồi có thể đ•ợc định nghĩa
nh• giao của một số hữu hạn những nửa - không gian, cho mỗi mặt. Một đa diện
không lồi có thể đ•ợc định nghĩa nh• hợp của một số hữu hạn các đa diện lồi. Vị từ
(x, y, z) có thể đ•ợc định nghĩa t•ơng tự là TRUE nếu ( x, y, z) O, và FALSE
trong tr•ờng hợp ng•ợc lại.
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
32
2.2.2. mô hình nửa Đại số
Trong những mô hình đa giác và đa diện, f là một hàm tuyến tính.
Trong tr•ờng hợp của một mô hình nửa đại số của không gian 2D, f là đa thức
với những hệ số bất kỳ của hai biến thực x và y. Trong không gian 3 chiều, f là một
đa thức với ba biến thực x, y, z. Lớp những mô hình nửa đại số bao gồm cả hai mô
hình đa diện và đa giác, mà sử dụng tr•ớc hết cho đa diện. Một tập hợp điểm xác
định bởi một mẫu đa thức đơn đ•ợc gọi một tập hợp đại số; Một tập hợp điểm mà
có thể thu đ•ợc bởi một số hữu hạn của những phép hợp và phép giao những tập hợp
đại số đ•ợc gọi một tập nửa đại số.
Xem xét tr•ờng hợp của không gian 2D. Một biểu diễn 3 chiều có thể đ•ợc
định nghĩa sử dụng những mẫu đại số có mẫu dạng:
Hình 2.7 : (a) Hàm f đ•ợc sử dụng để phân chia R2 vào trong hai vùng.
(b) Vùng “ mặt ” được mô hình bằng cách sử dụng bốn mẫu đại số.
Ví dụ 2.1 cho f = x2 + y2 - 4. Trong tr•ờng hợp này, H thay mặt đ•ờng tròn
bán kính r =2, tâm đ•ợc đặt đúng ở gốc. Điều này t•ơng ứng tới tập hợp của những
điểm (x, y) cho f(x, y) = 0, nh• đ•ợc miêu tả trong Hình 2.7a.
(2.10)
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
33
Ví dụ 2.2 (khuôn mặt) xem xét việc xây dựng một mô hình của vùng đậm
màu trong Hình 2.7b. Hãy cho vòng tròn ngoài có bán kính r1 và tâm đ•ợc đặt tại
gốc. Giả thiết “ đôi mắt ” có bán kính r2 và r3 và đ•ợc tâm ở tại (x2,y2) và (x3,y3),
t•ơng ứng cho “ miệng ” một hình ê-líp với trục chính a và trục phụ b và đ•ợc tâm
ở ( 0, y4).
Những hàm đ•ợc định nghĩa nh• sau:
Cho f2, f3, và f4, là những ph•ơng trình đ•ờng tròn và hình ê-líp đ•ợc nhân
với - 1 để sinh ra những mẫu đại số cho tất cả các điểm bên ngoài đ•ờng tròn hay
hình ê-líp. Vùng O đậm màu đ•ợc t•ơng ứng nh• sau:
Trong tr•ờng hợp của những mô hình nửa đại số, phép giao của những mẫu
không nhất thiết kết quả trong một tập con lồi W. Nói chung, nó có thể cần thiết để
hình thành O bởi việc lấy hợp và giao của những mẫu đại số.
Rõ ràng biểu diễn bằng mô hình nửa đại số có thể khái quát hóa dễ dàng
tr•ờng hợp không gian 3 chiều.
Dạng đại số nguyên thuỷ của mẫu :
Có thể sử dụng để định nghĩa một biểu diễn của một ch•ớng ngại 3 chiều O và một
vị từ lôgíc . Những ph•ơng trình (2.10) và (2.13 ) đủ để biểu thị bất kỳ mô hình
nào cần quan tâm. Có thể định nghĩa mẫu theo nhiều cách khác dựa vào những quan
hệ khác nhau, nh• :
(2.11)
(2.12)
(2.13)
(2.14)
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
34
f(x, y, z) 0, f(x, y, z) = 0, f(x, y,z) < 0, f(x, y, z) = 0, và f(x, y, z) 0
Xét mẫu:
có thể biểu diễn theo cách khác nh• - f(x, y, z) 0, và - f có thể đ•ợc xem xét nh•
một hàm đa thức mới của x, y, z. Cho một ví dụ qua hệ bằng:
Có thể thay H = H1 H2, với :
và
Quan hệ < tăng thêm sức mạnh có ý nghĩa nào đó khi xây dựng những mô hình
không chứa đ•ờng biên ngoài. Chú ý rằng phần đậm màu luôn luôn ở bên trái khi đi
theo những mũi tên.
Hình 2.8 : Một đa giác với những lỗ tr...
Download miễn phí Luận văn Một số phương pháp chính xác lập lộ trình chuyển động cho robot
Mục lục
CHươNG I: GIơI THIệU BàI TOáN Lậ P TRìNH CHO ROBOT . 7
1.1. Robot nhân tạo . 7
1.2. Bài toán lập lộ trình . 9
1.3.Ví dụ và những ứng dụng về lộ trình Robot . 12
1.4. Những thành phần cơ bản của việc lập lộ trình . 16
1.5. Giải thuật, ng ười lập lộ trình và lộ trình . 17
1.6. Kết luận . 23
Chương IIư cấu hình không gian trạng thái . 24
2.1.Các Khái niệm cấu hình không gian . 24
2.1.1. Chướng ngại (Obstacle) . 24
2.1.2. Không gian trống ( Free Spaceư Cfree) . . 25
2.2. Mô hình cấu hình . 26
2.2.1. Mô hình hình học . 26
2.2.2. Mô hình nửa Đại số . 32
2.3. Các phép biến đổi của robot . 35
2.4. Không gian cấu hình ch ướng ngại vật . 37
2.5ư Định nghĩa chính xác về vấn đề lập lộ trình chuyển động . 38
2.6. Một số mô hình Cobs. 39
2.7. Kết luận . 47
Chương IIIưMột số phương pháp chính xác lập lộ trình chuyển Động . 48
3.1.Giới thiệu chung . 48
3.2. Biểu diễn không gian chướng ngại vật . 50
3.3. Một số giải thuật lập lộ trình chính xác cho robot . 53
3.3.1 . Roadmap Visibility Graph – Đồ thị tầm nhìn . 53
3.3.2. Vertical Cell Decomposition ( phân ly Ô dọc ) . 59
Kết luận . 68
Tài liệu tham khảo. 69
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung:
biểu thị O sao cho tối thiểu nhất các mẫu .ở đây một logic vị từ đã đ•ợc định nghĩa nh• sau: : W {TRUE, FALE}.
Hàm trả lại giá trị TRUE khi một điểm trong W nằm bên trong O, và ng•ợc lại là
False . Cho một đ•ờng thẳng f(x, y ) = 0 để e(x, y) biểu thị một vị từ lôgíc trả lại
giá trị TRUE nếu f(x, y) = 0, và ng•ợc lại là FALSE. Một vị từ t•ơng ứng tới một
vùng đa giá c lồi đ•ợc biểu diễn bởi các phép hội nh• sau:
Vị từ (x, y) trả về giá trị TRUE nếu điểm (x, y) nằm trong vùng đa giá c lồi,
ng•ợc lại là FALSE. Một vùng ch•ớng ngại mà gồm có n đa giác lồi đ•ợc biểu diển
bởi tuyển nh• sau:
(2.5)
(2.6)
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
30
Mặc dầu tồn tại những ph•ơng pháp hiệu quả hơn, có thể kiểm tra một điểm
( x, y) nằm trong O với thời gian O(n), trong đó n là số mẫu mà xuất hiện trong biểu
diễn của O ( Mỗi mẫu đ•ợc •ớc l•ợng trong hằng số thời gian). Bất kỳ mệnh đề
lôgíc phức tạp đến đâu đều có thể đ•ợc tách nhỏ thành những chuẩn tuyển ( Đây th-
ường được gọi “ tổng của những tích ” trong khoa học máy tính). Như vậy chúng ta
có thể nói bất kỳ một không gian O luôn luôn đ•ợc biểu diễn bằng hợp của hữu hạn
các phép giao những mẫu.
2.2.1.2- Mô hình đa diện:
Trong không gian ba chiều W = R3 , những khái niệm có thể đ•ợc khái quát
hóa rất tốt từ tr•ờng hợp không gian 2D bởi việc thay thế đa giác bằng khối đa d iện
và thay thế nửa mặt phẳng bởi nửa không gian mẫu.
Một ranh giới biểu diễn có thể đ•ợc định nghĩa d•ới dạng ba đặc tr•ng : đỉnh,
cạnh, và mặt. Một vài cấu trúc dữ liệu đ•ợc đ•a ra để biểu diễn đa diện, ví dụ, cấu
trúc dữ liệu chứa ba kiểu bản ghi : đỉnh, mặt và nửa cạnh (một nửa cạnh là cạnh có
h•ớng).
Giả sử O là một đa diện lồi, nh• trong Hình 2.5. Một biểu diễn ba chiều có
thể đ•ợc xây dựng từ những đỉnh. Mỗi mặt của O có ít nhất ba đỉnh dọc theo ranh
giới của nó. Giả thiết rằng những đỉnh này không cộng tuyến, một ph•ơng trình của
mặt phẳng đi qua chúng có dạng:
ax + by + cz + d = 0 (2.7)
trong đó a, b, c, d R là những hằng số.
Một lần nữa, f có thể xây dựng bằng ánh xạ f : R3 R và
f(x, y, z) = ax + by + cz + d. (2.8)
với m mặt. Cho mỗi mặt của O, một nửa - không gian Hi đ•ợc định nghĩa nh• một
tập con của W:
(2.9)
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
31
Điều quan trọng là chọn fi để nó giữ những giá trị âm ở trong đa diện. Trong
mô hình đa giác, để thích hợp với định nghĩa f i là việc xuất phát đi vòng quanh biên
theo thứ tự ng•ợc chiều kim đồng hồ. Trong tr•ờng hợp một đa diện, ranh giới của
mỗi mặt là các cạnh cũng đ•ợc lấy ng•ợc chiều kim đồng hồ. (Hình 2.6b)
Ph•ơng trình cho mỗi mặt đ•ợc xác định nh• sau: Chọn ba đỉnh liên tiếp p1,
p2, p3 (không đ•ợc cộng tuyến ) theo thứ tự ng•ợc chiều kim đồng hồ. Cho v 12 biểu
thị vectơ từ p1 tới p2, v23 biểu thị vectơ từ p2 đến p3. Tích v = v12 x v23 luôn luôn là
một vectơ nằm trong mặt phẳng gọi là vectơ hồi. Véc tơ [a b c] song song với mặt
phẳng. Nếu những thành phần của nó đ•ợc chọn là a = v[1], b=v[2], c = v[3], thì
f(x, y, z) = 0 cho mọi điểm trong nửa - không gian chứa đa diện.
Hình 2.6: (a) Mô tả một đa diện d•ới dạng mặt, cạnh, và đỉnh. ( b) Những cạnh
của mỗi mặt có thể đ•ợc l•u trữ trong chu trình theo thứ tự ng•ợc chiều kim đồng
hồ.
Trong tr•ờng hợp của một đa giác mẫu, một đa diện lồi có thể đ•ợc định nghĩa
nh• giao của một số hữu hạn những nửa - không gian, cho mỗi mặt. Một đa diện
không lồi có thể đ•ợc định nghĩa nh• hợp của một số hữu hạn các đa diện lồi. Vị từ
(x, y, z) có thể đ•ợc định nghĩa t•ơng tự là TRUE nếu ( x, y, z) O, và FALSE
trong tr•ờng hợp ng•ợc lại.
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
32
2.2.2. mô hình nửa Đại số
Trong những mô hình đa giác và đa diện, f là một hàm tuyến tính.
Trong tr•ờng hợp của một mô hình nửa đại số của không gian 2D, f là đa thức
với những hệ số bất kỳ của hai biến thực x và y. Trong không gian 3 chiều, f là một
đa thức với ba biến thực x, y, z. Lớp những mô hình nửa đại số bao gồm cả hai mô
hình đa diện và đa giác, mà sử dụng tr•ớc hết cho đa diện. Một tập hợp điểm xác
định bởi một mẫu đa thức đơn đ•ợc gọi một tập hợp đại số; Một tập hợp điểm mà
có thể thu đ•ợc bởi một số hữu hạn của những phép hợp và phép giao những tập hợp
đại số đ•ợc gọi một tập nửa đại số.
Xem xét tr•ờng hợp của không gian 2D. Một biểu diễn 3 chiều có thể đ•ợc
định nghĩa sử dụng những mẫu đại số có mẫu dạng:
Hình 2.7 : (a) Hàm f đ•ợc sử dụng để phân chia R2 vào trong hai vùng.
(b) Vùng “ mặt ” được mô hình bằng cách sử dụng bốn mẫu đại số.
Ví dụ 2.1 cho f = x2 + y2 - 4. Trong tr•ờng hợp này, H thay mặt đ•ờng tròn
bán kính r =2, tâm đ•ợc đặt đúng ở gốc. Điều này t•ơng ứng tới tập hợp của những
điểm (x, y) cho f(x, y) = 0, nh• đ•ợc miêu tả trong Hình 2.7a.
(2.10)
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
33
Ví dụ 2.2 (khuôn mặt) xem xét việc xây dựng một mô hình của vùng đậm
màu trong Hình 2.7b. Hãy cho vòng tròn ngoài có bán kính r1 và tâm đ•ợc đặt tại
gốc. Giả thiết “ đôi mắt ” có bán kính r2 và r3 và đ•ợc tâm ở tại (x2,y2) và (x3,y3),
t•ơng ứng cho “ miệng ” một hình ê-líp với trục chính a và trục phụ b và đ•ợc tâm
ở ( 0, y4).
Những hàm đ•ợc định nghĩa nh• sau:
Cho f2, f3, và f4, là những ph•ơng trình đ•ờng tròn và hình ê-líp đ•ợc nhân
với - 1 để sinh ra những mẫu đại số cho tất cả các điểm bên ngoài đ•ờng tròn hay
hình ê-líp. Vùng O đậm màu đ•ợc t•ơng ứng nh• sau:
Trong tr•ờng hợp của những mô hình nửa đại số, phép giao của những mẫu
không nhất thiết kết quả trong một tập con lồi W. Nói chung, nó có thể cần thiết để
hình thành O bởi việc lấy hợp và giao của những mẫu đại số.
Rõ ràng biểu diễn bằng mô hình nửa đại số có thể khái quát hóa dễ dàng
tr•ờng hợp không gian 3 chiều.
Dạng đại số nguyên thuỷ của mẫu :
Có thể sử dụng để định nghĩa một biểu diễn của một ch•ớng ngại 3 chiều O và một
vị từ lôgíc . Những ph•ơng trình (2.10) và (2.13 ) đủ để biểu thị bất kỳ mô hình
nào cần quan tâm. Có thể định nghĩa mẫu theo nhiều cách khác dựa vào những quan
hệ khác nhau, nh• :
(2.11)
(2.12)
(2.13)
(2.14)
Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn
34
f(x, y, z) 0, f(x, y, z) = 0, f(x, y,z) < 0, f(x, y, z) = 0, và f(x, y, z) 0
Xét mẫu:
có thể biểu diễn theo cách khác nh• - f(x, y, z) 0, và - f có thể đ•ợc xem xét nh•
một hàm đa thức mới của x, y, z. Cho một ví dụ qua hệ bằng:
Có thể thay H = H1 H2, với :
và
Quan hệ < tăng thêm sức mạnh có ý nghĩa nào đó khi xây dựng những mô hình
không chứa đ•ờng biên ngoài. Chú ý rằng phần đậm màu luôn luôn ở bên trái khi đi
theo những mũi tên.
Hình 2.8 : Một đa giác với những lỗ tr...