§¹i häc Th¸i Nguyªn
Khoa c«ng nghÖ th«ng tin
NguyÔn thÞ thu thuû
Mét sè phƯƠNG ph¸p chÝnh x¸c lËp lé tr×nh
chuyÓn ®éng cho robot
Chuyªn ngµnh: Khoa häc m¸y tÝnh
M· sè: 60.48.01
LuËn v¨n th¹c sÜ c«ng nghÖ th«ng tin
ngƯỜI HƯỚNG dÉn khoa häc:
PGS – TS §Æng Quang ¸
Th¸i Nguyªn 2008
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2
MỤC LỤC
MỤC LỤC .............................................................................................................................. 2
DANH MỤC CÁC H×NH VẼ, ĐỒ THỊ ................................................................................ 4
MỞ ĐẦU................................................................................................................................ 5
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è gii 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 kho.................................................................................................... 69
Phô lôc 1 - Chƣơng tr×nh thö nghiÖm Visibility Graph ............................................... 70
Phô lôc 2- Chƣơng tr×nh thö nghiÖm Vertical Cell Decomposition ..................73
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
3
Danh môc c¸c h×nh vÏ vµ ®å thÞ
H×nh 1.1 C¸c thµnh phÇn cÊu thµnh Robot ......................................................................9
H×nh 1.2 : Khèi Rubik (a), Bµi to¸n xÕp h×nh (b)...........................................................12
H×nh1.3: T×m gii thuËt kÐo hai thanh thÐp t¸ch ra ......................................................12
H×nh 1.4: Sö dông Robot di ®éng ®Ó di chuyÓn mét Piano ...........................................13
H×nh 1.5: Thö nghiÖm mét sè Robot tr¸nh vËt cn........................................................14
H×nh 1.6:Robot tù x©y dùng bn ®å m«i trường vµ x¸c®Þnh vÞ trÝ cña chÝnh nã .....14
H×nh 1.7: M¸y Turing........................................................................................................17
H×nh 1.8: Gianh giíi gi÷a m¸y vµ m«i trường ..............................................................18
H×nh 1.9: Robot víi nh÷ng c«ng t¾c ®ãng vai trß như mét m¸y Turing .....................19
H×nh 1. 10 :Mèi quan hÖ gi÷ lé tr×nh vµ ngườii lËp lé tr×nh ........................................20
H×nh 1.11: Mét c¸ch tiÕp cËn ci tiÕn trong kü thuËt r«b«t .........................................22
H×nh 1.12- M« h×nh cã thø bËc ......................................................................................22
H×nh 2.1: CÊu h×nh kh«ng gian ........................................................................................25
H×nh 2. 2: Mét Robot ®iÓm di chuyÓn trong kh«ng gian 2D, C-space lµ R2 .............26
H×nh 2.3: Mét robot ®iÓm di chuyÓn trong kh«ng gian 3D, C-space lµ R3.................26
H×nh 2.4 - C¸ch x¸c ®Þnh mét ®a gi¸c låi b»ng phÐp giao cña nh÷ng nöa - mÆt
ph¼ng) .................................................................................................................................27
H×nh 2.5- DÊu hiÖu cña f(x, y) ph©n chia R 2 .................................................................28
H×nh 2.6: M« t¶ mét ®a diÖn ...........................................................................................31
H×nh 2.7 : f được sö dông ®Ó ph©n chia R2 vµo trong hai vïng .................................32
H×nh 2.8 : BiÓu diÔn m« h×nh ®a gi¸c víi nh÷ng lç trèng .............................................34
H×nh 2.9: Hai c¸ch gi¶i thÝch cho phÐp tÞnh tiÕn ...........................................................35
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
4
H×nh 2.10 - Kh¸i niÖm vÒ C-space vµ nhiÖm vô lµ t×m mét đường tõ qI ®Õn qG
trong Cfree víi C = Cfree Cobs.........................................................................................38
H×nh 2.11 : Mét chướng ng¹i kh«ng gian C- mét chiÒu ..............................................40
H×nh 2.12: Mét robot A tam gi¸c vµ mét chướng ng¹i h×nh ch÷ nhËt....................41
H×nh 2.13: X©y dùng Cobs trong phÐp tÞnh tiÕn ..............................................................42
H×nh 2.14 : LÊy vµ s¾p xÕp c¸c vÐc t¬ ph¸p tuyÕn .......................................................42
H×nh 2.15:Hai kiÓu va ch¹m ph¸t sinh c¹nh cho Cobs
...................................................43
H×nh 2.16 : Tr¹ng th¸i va ch¹m khi n vµ v vu«ng gãc ..................................................43
H×nh 2.17: Ba kiÓu tiÕp xóc kh¸c nhau sinh ra c¸c lo¹i Cobs kh¸c nhau....................44
H×nh 2.18: X©y dùng Cobs cho phÐp quay ........................................................................45
H×nh 3.1: Mét m« h×nh kh«ng gian được chØ râ bëi bèn ®a gi¸c gi¸c cã hướng ....51
H×nh 3.2 : X©y dùng Roadmap Visibility Graph ..........................................................54
H×nh 3.3: qI vµ qG ®- îc nèi tíi tÊt c ®Ønh cã thÓ thÊy cña roadmap .......................54
H×nh 3.4 : Đường ®i ng¾n nhÊt trong Roadmap s. ........................................................55
H×nh 3.5 :S¬ ®å thuËt to¸n Visibility Graph...................................................................57
H×nh 3.6: Mét sè đường dÉn gi¶i ph¸p cña phương ph¸p Visibility Graph ............58
H×nh 3.7 : Bèn trường hîp tæng qu¸t cña tia ph©n ly ...............................................60
H×nh 3.8 : Sö dông phương ph¸p ph©n ly « däc ®Ó x©y dùng mét roadmap .............60
H×nh 3.9 : Roadmap b¾t nguån tõ sù ph©n ly « däc ......................................................61
H×nh 3.10: VÝ dô vÒ ®- êng dÉn gii ph¸p .......................................................................62
H×nh 3.11 : VÝ dô cã 14 sù kiÖn ........................................................................................63
H×nh 3.12: T×nh tr¹ng cña L ®- îc chØ ra sau mçi 14 sù kiÖn xuÊt hiÖn .....................64
H×nh 3.13: S¬ ®å thuËt to¸n ph- ¬ng ph¸p Cell Decomposition ................................66
H×nh 3.13: Mét sè đường ®i gi¶i ph¸p cña pp Cell Decompsition ..........................67
Số hóa bởi Trung tâm Học liệu – Đại học 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) hƣớng dÉn lé tr×nh cho robot
di chuyÓn qua m«i trƣờng víi mong muèn ®Õn ®- îc ®Ých mµ kh«ng bÞ l¹c hay va
vµo nh÷ng ®èi tƣợng kh¸c.
Th«ng thƣờng, mét lé tr×nh ®- îc lËp trƣớc ®Ó 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 phi ®-î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 trƣờng hiÖn t¹i ®Ò xö lý c¸c chƣớng ng¹i ch- a biÕt khi
robot b¨ng qua m«i trƣờng.
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¬ bn ®Ó 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
®Ó gii quyÕt bµi to¸n nh- øng dông gii 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 “Một số phương pháp chính
xác lập lộ trình chuyển động cho Robot”. Néi dung c¬ b¶n cña luËn v¨n tèt
nghiÖp gåm cã ba chƣơng:
Chương 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¬ bn 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.
Chương 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µ