Một số phương pháp chính xác lập lộ trình chuyển động cho rôbôt

S húa bi Trung tõm Hc liu i hc Thỏi Nguyờn http://www.lrc-tnu.edu.vn
5
Mở đầu
Tìm ng là một khoa học (hay nghệ thuật) hng dẫn lộ trình cho robot
di chuyển qua môi trng với mong muốn đến đ-ợc đích mà không bị lạc hay va
vào những đối tng khác.
Thông thng, một lộ trình đ-ợc lập trc để dẫn dắt robot đến đích của
nó. Với ph-ơng pháp này, môi tr-ờng robot đi qua phải đ-ợc biết hoàn toàn và
không thay đổi, robot có thể đi theo một cách hoàn hảo. Hạn chế của việc vạch lộ
trình tr-ớc đòi hỏi việc nghiên cứu tìm hiểu việc vạch lộ trình nội tại, phụ thuộc vào
các tri thức thu đ-ợc từ môi trng hiện tại đề xử lý các chng ngại ch-a biết khi
robot băng qua môi trng.
Trên thế giới hiện nay robot là một lĩnh vực đ-ợc hết sức quan tâm. Bài toán
lập lộ trình cho robot là bài toán cơ bản để thiết kế chế tạo Robot, do vậy việc tìm
hiểu bài toán và nghiên cứu các ph-ơng pháp vạch lộ trình là hết sức quan trọng cần
thiết cho sự phát triển lĩnh vực thiết kế và chế tạo Robot. Đã có một số nghiên cứu
để giải quyết bài toán nh- ứng dụng giải thuật di truyền lập ch-ơng trình tiến hoá,
xây dựng một số các thuật toán cho bài toán, nh-ng đây vẫn là một vấn đề mở đang
rất đ-ợc quan tâm. Đặc biệt trong n-ớc, đây là một lĩnh vực còn t-ơng đối mới mẻ,
hầu nh- ch-a có các tài liệu đề một cách đầy đủ về lĩnh vực này.
Nhận thức đ-ợc vấn đề đó và với sự gợi ý định h-ớng của PGS .TS
Đặng Quang á em đã chọn nghiên cứu đề tài Mt s phng phỏp chớnh
xỏc lp l trỡnh chuyn ng cho Robot. Nội dung cơ bản của luận văn tốt
nghiệp gồm có ba chng:
Chng 1- Trình bày tổng quan bài toán lập lộ trình cho Robot đó là
các khái niệm cơ bản về Robot, và bài toán về Robot, thuật toán và một số ví
dụ ứng dụng bài toán lập lộ trình cho Robot.
Chng 2- Trình bày các khái niệm về cấu hình không gian trạng
thái, cách biểu diễn không gian trong bài toán lập lộ trình cho robot. Đây là

S húa bi Trung tõm Hc liu i hc Thỏi Nguyờn http://www.lrc-tnu.edu.vn
6
các khái niệm cơ sở để biểu diễn đ-ợc bài toán cho các giải thuật lập lộ trình
chuyển động cho robot.
Chng 3- Đi sâu nghiên cứu một số ph-ơng pháp chính xác lập lộ
trình chuyển động cho Robot. Cụ thể đó là hai ph-ơng pháp ROADMAP
VISIBILITY GRAPH và CELL DECOMPSITION. Đây là những cách tiếp
cận tổ hợp tới việc lập lộ trình chuyển động để tìm thấy những đ-ờng đi xuyên
qua không gian cấu hình liên tục mà không dùng đến những thuật toán xấp xỉ.
Qua luận văn này em xin chân thành cảm ơn: PGS .TS Đặng Quang á -
Viện Công nghệ thông tin đã tận tình giúp đỡ, động viên, định h-ớng, h-ớng dẫn
em nghiên cứu và hoàn thành luận văn này. Em xin cảm ơn các thầy cô giáo trong
viện Công nghệ thông tin, các thầy cô giáo khoa Công nghệ thông tin ĐH Thái
nguyên, đã giảng dạy và giúp đỡ em trong hai năm học qua, cảm ơn sự giúp đỡ
nhiệt tình của các bạn đồng nghiệp .


Thái Nguyên 11/2008
Ngi viết luận văn

Nguyễn Thị Thu Thuỷ


S húa bi Trung tõm Hc liu i hc Thỏi Nguyờn http://www.lrc-tnu.edu.vn
7


Ch-ơng I
Giới thiệu bài toán lập lộ trình cho Robot
1.1. ROBOT NHN TạO.
Cựng vi s phỏt trin ca khoa hc, cụng ngh robot ngy cng c ng
dng rng rói trong cỏc lnh vc ca i sng xó hi. Chỳng cú th l nhng thit b
iu khin t ng trong cỏc dõy truyn cụng nghip, hoc cú th l nhng robot
lm vic trong nhng mụi trng phc tp m con ngi ụi khi khụng th tip cn
c nh: mụi trng nhit cao, ỏp sut ln hay ngoi khong khụng v tr.
Khụng ch cú vy robot cũn c ng dng rt nhiu trong i sng vớ d nh:
Robot lau dn sn nh, robot hng dn di chuyn, robot phc v trong cỏc to nh
cao tng, robot phu thut,
Robot c ng dng rng rói v cú nhiu tớnh nng u vit nh vy song
khụng phi ai cng cú th hiu v nguyờn lý ca nhng tỏc v m robot cú th thc
hin. Sau õy s l nhng trỡnh by s lc v nguyờn tc cu to v nguyờn lý lm
vic ca mt mobile robot.
1.1.1. Tng quan
V cu to: Robot phi dc trang b b cm nhn cm nhn cỏc thụng
tin v mụi trng nh: sensor, encoder. Cỏc b phn thc hin hnh ng:
bỏnh xe chuyn ng, cỏnh tay robot
Cỏc tri thc m robot cn c trang b l: Cu trỳc ca mụi trng lm
vic, cỏc hon cnh m robot cú th gp v cỏc hnh ng m robot cn thc
hin trong cỏc hon cnh ú, Cỏc tri thc ny cn phi c th hin mt
cỏch thớch hp sao cho thun tin cho vic lu tr, tỡm kim v suy din.

S húa bi Trung tõm Hc liu i hc Thỏi Nguyờn http://www.lrc-tnu.edu.vn
8
Cỏc kh nng ca robot: Robot cn cú kh nng phõn bit c cỏc i
tng m nú gp, thc hin cỏc thao tỏc, di chuyn an ton trong mụi trng
sao cho ng i l ti u v khụng va trm vi cỏc vt cn.
1.1.2. Gii phỏp thit k
thit k robot ta phi hon thin cỏc cụng vic sau:
Xem robot nh mt i tng lp trỡnh bao gm:
- D liu: Cỏc trng thỏi ca mụi trng lm vic, giỏ tr ca sensor,
encoder
- Tỏc v: L tp cỏc hnh ng c bn m robot cú th thc hin nh: tin,
lựi, r trỏi, r phi,
Mụ hỡnh hoỏ mụi trng lm vic.
Mụ hỡnh hoỏ i tng robot s gp, x lý cỏc tỏc v trong mụi trng lm
vic, cựng vi vic x lý d liu v cỏc trng thỏi trong mụi trng.
Nhỳng cỏc gii thut tỡm ng v gii thut x lý s kin cho robot cú
mt ng i tt t v trớ ban u ti ớch v x lý cỏc tỡnh hung ngoi l
nh va chm.
Phõn chia v module hoỏ cỏc khi trờn robot.
Xõy dng cỏc thnh phn robot bao gm: Lp trỡnh, mch phn cng, c cu
c khớ. C ba quỏ trỡnh ny phi trin khai ng b vi nhau v chỳng cú tỏc
ng rt ln ti nhau, s hon thin phn ny l tin xõy dng phn
kia.
C ch hin th v Debug li qua cỏc giao tip Led/LCD hay vi PC.
Cỏc thnh phn cu thnh nờn robot cú th c mụ hỡnh hoỏ bi s sau:

S húa bi Trung tõm Hc liu i hc Thỏi Nguyờn http://www.lrc-tnu.edu.vn
9

Hỡnh 1.1. Các thành phần cấu thành Robot
Tất cả các thành phần trên góp phần cấu thành một Robot hoàn chỉnh. Ta có
thể ví các cơ cấu cơ khí giống nh- phần thể xác, các mạch điện tử giống nh- các
mạch máu, các noron thần kinh và các giác quan bên ngoài. Ch-ơng trình giống nh-
bộ não giúp điều khiển cơ thể thông qua hệ thống mạch.
1.2. BI TON Lập lộ trình.
Nền tảng quan trọng trong kỹ thuật rôbôt là xây dựng những giải thuật để
mô phỏng những nhiệm vụ bậc cao của con ng-ời vào trong những ngôn ngữ bậc
thấp của máy để có thể điều khiển robot di chuyển. Những thuật ngữ lập lộ trình và
quỹ đạo chuyển động th-ờng đ-ợc sử dụng trong vấn đề này. Việc lập lộ trình
chuyển động robot thông th-ờng không quan tâm nhiều đến lĩnh vực động lực học,
trọng tâm cơ bản của vấn đề này là tìm đ-ờng và di chuyển đến đích tránh sự va
trạm với môi tr-ờng xung quanh. Việc lập lộ trình quỹ đạo thực chất là lấy giải pháp
từ một giải thuật lập lộ trình chuyển động robot và xác định làm sao để di chuyển
theo giải pháp đó nh-ng ngoài ra còn phải chú trọng tới những hạn chế cơ khí của
robot.
Việc lập lộ trình là một vấn đề có nhiều ý nghĩa đối với những lĩnh vực khác
nhau:

S húa bi Trung tõm Hc liu i hc Thỏi Nguyờn http://www.lrc-tnu.edu.vn
10
Trong lý thuyết điều khiển, vấn đề này đ-ợc đề cập tới nh- việc thiết kế
những hệ thống vật lý mô tả bởi những ph-ơng trình vi phân. Những hệ thống đó có
thể bao gồm những hệ thống cơ khí nh- ô tô hoặc máy bay, những hệ thống điện nh-
- lọc tiếng ồn, hoặc cả những hệ thống xuất hiện trong nhiều lĩnh vực đa dạng khác
nh- hóa học, kinh tế học, và xã hội học. Tr-ớc đây, lý thuyết điều khiển là điều
khiển mờ phản hồi, cho phép một sự hồi đáp có khả năng thích ứng trong thời gian
thực hiện, tập trung về sự ổn định, mà bảo đảm rằng vấn đề động lực học không gây
cho hệ thống trở nên lộn xộn mất điều khiển. Một tiêu chuẩn quan trọng cho sự tối -
-u hóa để tối giản tiêu thụ tài nguyên, nh- năng l-ợng hoặc thời gian. Trong các tài
liệu lý thuyết điều khiển gần đây, việc lập lộ trình chuyển động đôi khi quy dẫn đến
xây dựng đầu vào cho một hệ thống động lực phi tuyến để điều khiển robot từ một
vị trí ban đầu đến một đích xác định .
Trong trí tuệ nhân tạo, những thuật ngữ việc lập lộ trình và việc lập lộ trình
AI đảm nhiệm một nhiệm vụ riêng. Thay vào việc di chuyển một pianô qua một
không gian liên tục, thì vấn đề lập lộ trình chuyển động cho robot trong trí tuệ nhân
tạo với những nhiệm vụ giải quyết một bài toán, nh- bài toán Rubik hoặc một bài
toán sliding-tile puzzle (xếp hình). Lộ trình trong trí tuệ nhân tạo đ-ợc định nghĩa
là một tập hữu hạn của những hành động có thể đ-ợc áp dụng cho một tập hợp
riêng biệt những trạng thái và xây dựng một giải pháp thích hợp cho dãy những
hành động đó.
Trong lịch sử, việc lập lộ trình đã xem xét trên những góc độ khác nhau giải
quyết những vấn đề khác nhau trong từng lĩnh vực; tuy nhiên, trong những năm gần
đây thì sự phân biệt này có vẻ mờ nhạt dần. Trong phạm vi rộng những vấn đề đề
cập trong thuật ngữ lập lộ trình đã đ-ợc áp dụng trong tất cả các lĩnh vực trí tuệ
nhân tạo, lý thuyết điều khiển, và kỹ thuật rôbôt. Vài nguyên lý cơ bản chung của
những vấn đề lập lộ trình sẽ đ-ợc xem xét, nh-ng tr-ớc hết chúng ta coi việc lập lộ
trình nh- một nhánh của giải thuật. Từ đây, chúng ta nghiên cứu những giải thuật
lập lộ trình. Trọng tâm là thuật toán và những vấn đề cài đặt một số ph-ơng pháp
lập lộ trình. Ngoài ra, có nhiều khái niệm không hẳn là thuật toán nh-ng có tác

S húa bi Trung tõm Hc liu i hc Thỏi Nguyờn http://www.lrc-tnu.edu.vn
11
dụng bổ trợ rất nhiều trong việc xây dựng những mô hình, giải quyết, và phân tích
vấn đề lập lộ trình. Đó là các vấn đề để trả lời cho những câu hỏi sau:
- Thế nào là một lộ trình?
- Một lộ trình đ-ợc mô tả nh- thế nào?
- Nó đ-ợc cài đặt nh- thế nào trong máy tính?
- Nh- thế nào đ-ợc cho là hoàn tất?
- Chất l-ợng của của một lộ trình đ-ợc đánh giá nh- thế nào?
- Ai hoặc cái gì sẽ sử dụng nó?
ở đây, khái niệm user của lộ trình cũng sẽ th-ờng xuyên đ-ợc nhắc đến nh- khái
niệm robot hoặc nhà chế tạo. Trong trí tuệ nhân tạo và những lĩnh vực liên quan,
ng-ời ta sử dụng thuật ngữ này phù hợp với từ sinh ra một tác nhân thông minh hoặc
tác nhân phần mềm. Trong lý thuyết điều khiển th-ờng nhắc tới các nhà chế tạo nh-
một ng-ời giám sát, kiểm tra. Trong ngữ cảnh lập lộ trình này đôi khi đ-ợc nhắc tới
nh- một chính sách hoặc luật điều khiển. Trong một ngữ cảnh lý thuyết trò chơi, nó
có thể có ý nghĩa để h-ớng tới những nhà sản xuất chế tạo nh- những bộ chơi.
Những ngôn ngữ nh- robot, đại diện, và ng-ời giám sát có thể thay thế lẫn nhau.
Tại sao phải nghiên cứu những giải thuật lập lộ trình?
Có ít nhất hai lý do cần phải giải quyết cho vấn đề này. Tr-ớc hết, đó là những trò
chơi để máy có thể giải quyết những vấn đề gây khó khăn lớn cho con ng-ời. Điều
này đòi hỏi những thách thức cần phải thiết kế những giải thuật hiệu quả, và phát
triển và bổ sung các mô hình lập lộ trình. Thứ hai, việc lập lộ trình với những giải
thuật đã đạt đ-ợc những thành công lớn trong cả lý thuyết và thực tế ở các lĩnh vực
khác nhau nh- kỹ thuật rôbôt, thiết kế sản xuất kiểu mẫu thuốc, và những ứng dụng
trong không gian vũ trụ. Sự phát triển nhanh trong vài năm gần đây cho thấy những
ứng dụng ngày càng hấp dẫn hơn. Điều đó đang thúc đẩy mạnh việc học tập và
nghiên cứu những giải thuật lập lộ trình và góp phần cho sự phát triển và sử dụng
chúng.


S húa bi Trung tõm Hc liu i hc Thỏi Nguyờn http://www.lrc-tnu.edu.vn
12
1.3. Ví dụ và những ứng dụng về lộ trình Robot

Hình 1.2 : Khối Rubik (a), Bài toán xếp hình (b), và những bài toán xếp hình liên
quan là những ví dụ khác nhau của vấn đề lập một chiến l-ợc lộ trình đầu tiên.


Hình 1.3. Tìm một giải thuật với mục đích sẽ kéo hai thanh thép tách ra .
Ví dụ này đ-ợc gọi Alpha 1.0 Puzzle Bài toán này đ-ợc Boris Yamrom đề xuất và
nh- một chuẩn đánh giá chính nghiên cứu bởi Nancy Amato tại tr-ờng đại học
Texas A&M. Giải pháp cho bài toán này đ-ợc James Kuffner đề xuất.
Việc lập lộ trình chuyển động trong bài toán xếp hình trong Hình 1.2 có thể
dễ dàng thực hiện bởi vì tính đều đặn và đối xứng của những thành phần tham gia
vào di chuyển. Bài toán ở Hình 1.3 lại đ-a ra một vấn đề không có những thuộc tính
trên và đồng thời yêu cầu lập lộ trình trong một không gian liên tục. Đây chính là
những vấn đề cần đ-ợc giải quyết trong kỹ thuật lập lộ trình chuyển động. Mặc dù
vấn đề này có vẻ chỉ đơn thuần là những trò giải trí, những vấn đề t-ơng tự xuất hiện

S húa bi Trung tõm Hc liu i hc Thỏi Nguyờn http://www.lrc-tnu.edu.vn
13
trong những ứng dụng quan trọng. Tri thức chuyển động không chỉ hoàn toàn là trò
giải trí, vấn đề này đ-ợc đ-a vào bài toán khác nh- chuyển một đàn pianô qua một
căn phòng bằng cách sử dụng ba robot di động với cánh tay thao tác của chúng. Cần
phải tránh sự va chạm giữa những robot với những đồ đạc khác. Vấn đề sẽ phức tạp
khi những robot, pianô, và không gian xung quanh những mẫu dây chuyền động học
khép kín, mà không gian ch-a đ-ợc nhận biết rõ ràng.

Hình 1.4- Sử dụng những robot di động để di chuyển một Pianô
Tìm đ-ờng cho những robot di động: Một nhiệm vụ phổ biến cho những robot di
động là đòi hỏi chúng tìm đ-ờng đi trong môi tr-ờng trong nhà ( Hình 1.4a). Một
robot có thể đ-ợc yêu cầu để thực hiện những nhiệm vụ nh- xây dựng một bản đồ
của môi tr-ờng, xác định vị trí chính xác của nó bên trong một bản đồ, đích cần đến.
Đa số các robot hành động bất chấp tình trạng không chắc chắn. Tại một cực
trị, nếu xuất hiện mà có nhiều cảm biến thì có lợi bởi vì nó có thể cho phép - ớc
l-ợng chính xác môi tr-ờng và robot, xây dựng một bản đồ của môi tr-ờng của nó
là tiền đề của nhiều hệ thống hiện nay, đây là một lựa chọn đ-ợc -a chuộng cho
việc phát triển những robot đáng tin cậy hoàn thành những nhiệm vụ đặc biệt và chi
phí t-ơng đối thấp.

S húa bi Trung tõm Hc liu i hc Thỏi Nguyờn http://www.lrc-tnu.edu.vn
14

Hình 1.5: (a) Thử nghiệm thành công một số robot di động định h-ớng trong một
môi tr-ờng trong nhà khi phải tránh những sự va chạm với những bức t-ờng và
tránh lẫn nhau. (b) Sử dụng một đèn lồng để tìm kiếm những ng-ời mất tích trong
một hang.

Hình 1.6 : Một robot di động đáng tin cậy xây dựng tốt một bản đồ về môi tr-ờng
của nó (Phòng thí nghiệm nghiên cứu Intel) trong khi đồng thời cục bộ hóa vị trí
của chính nó. Điều này đ-ợc hoàn thành bởi sử dụng sensors laze quét thực hiện
Bayesian hiệu quả để tính toán trên thông tin về khoảng cách.
Trò chơi ẩn dấu và tìm kiếm: Một nhiệm vụ quan trọng cho một robot di động là
chơi trò chơi ẩn dấu và tìm kiếm. Hãy t-ởng t-ợng vào trong một hang hoàn toàn
tối. Bạn đ-ợc đ-a cho một chiếc đèn lồng và yêu cầu để tìm kiếm những ng-ời ở đó

Xem chi tiết: Một số phương pháp chính xác lập lộ trình chuyển động cho rôbôt