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

nh÷ng vect¬ v1 vµ v2. H×nh 2.18: X©y dùng Cobs cho phÐp quay. Sù ph¸t biÓu l•u t©m tíi h•íng cña nh÷ng vect¬ ph¸p tuyÕn cã thÓ t•¬ng ®•¬ng víi viÖc tr×nh bµy râ rµng gãc gi÷a n vµ v1, n vµ v2, ph¶i nhá h¬n p/2. Sö dông nh÷ng tÝch v« h•íng, n v1 = 0 vµ n v2 = 0. Nh• trong tr•êng hîp tÞnh tiÕn, ®iÒu kiÖn n v = 0 lµ ®iÒu kiÖn cña sù va ch¹m. Ta thÊy n phô thuéc vµo . Cho bÊt kú q C, nÕu n( ) v1 = 0, n( ) v2 = 0, vµ n( ) v(q) > q, th× q Cfree. §Ó cho Hf biÓu thÞ tËp hîp cña nh÷ng cÊu h×nh tháa m·n nh÷ng ®iÒu kiÖn nµy cã nghÜa lµ tËp c¸c ®iÓm trong Cfree. H¬n n÷a, mäi kiÓu kh¸c víi hai kiÓu tiÕp xóc EV vµ VE víi cã thÓ cã nhiÒu ®iÓm h¬n trong Cfree. Hf Cfree, phÇn bï cña nã C \ Hf, lµ mét tËp chøa Cobs ( Cobs C \ Hf ). §Ó cho HA = C \ Hf. Sö dông nh÷ng mÉu: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 46 §Ó cho . §iÒu ®ã cho biÕt nh÷ng Cobs HA, trõ phi HA cã chøa ®iÓm trong Cfree. T×nh tr¹ng t•¬ng tù ®Ó x©y dùng mét m« h×nh cña mét ®a gi¸c låi tõ nh÷ng nöa - mÆt ph¼ng. Trong sù thiÕt ®Æt hiÖn thêi, bÊt kú cÊu h×nh nµo bªn ngoµi cña HA ph¶i thuéc trong Cfree. NÕu HA giao víi tÊt c¶ nh÷ng tËp hîp cho mçi tiÕp xóc kiÓu EV vµ kiÓu VE, th× kÕt qu¶ lµ Cobs. Mçi tiÕp xóc cã c¬ héi ®Ó lo¹i bá mét phÇn cña C free tõ sù xem xÐt. DÇn dÇn, ®¹t tíi møc ®é tõng phÇn cña Cfree ®•îc lo¹i bá ®Ó nh÷ng cÊu h×nh duy nhÊt cßn l¹i ph¶i thuéc trong Cobs. Víi bÊt kú kiÓu va ch¹m EV nµo (H1 H2) \ H3 Cfree. Ph¸t biÓu t•¬ng tù cho nh÷ng va ch¹m kiÓu VE. Mét vÞ tõ l«gÝc, cã thÓ x©y dùng ®Ó x¸c ®Þnh q Cobs víi thêi gian tuyÕn tÝnh theo sè nh÷ng mÉu cña Cobs. Mét vÊn ®Ò quan träng cßn l¹i. BiÓu thøc n( ) kh«ng ph¶i lµ mét ®a thøc bëi v× cos( ) vµ sin( ) vÉn lµ nh÷ng ®èi t•îng trong ma trËn quay cña SO(2). NÕu mét ®a thøc cã thÓ lµ thay thÕ cho nh÷ng biÓu thøc nµy, th× mäi thø cã thÓ trë nªn cè ®Þnh v× biÓu thøc cña vect¬ ph¸p tuyÕn (kh«ng ph¶i lµ mét ®¬n vÞ chuÈn t¾c) vµ tÝch v« h•íng lµ c¶ hai hµm tuyÕn tÝnh, do ®ã thay ®æi ®a thøc vµo trong ®a thøc. Tuy nhiªn, mét c¸ch tiÕp cËn ®¬n gi¶n h¬n lµ sö dông nh÷ng sè phøc ®Ó ®¹i diÖn phÐp quay. Khi a + bi ®•îc sö dông ®Ó ®¹i diÖn phÐp quay, mçi ma trËn quay trong SO(2) ®•îc ®¹i diÖn nh• c«ng thøc vµ ma trËn 3x3 biÕn ®æi thuÇn nhÊt trë thµnh: (2.36) (2.37) (2.38) (2.39) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 47 Sö dông ma trËn nµy ®Ó thay ®æi mét ®iÓm [ x y 1 ] trong nh÷ng täa ®é ®iÓm (ax-by+xt, bx+ay+yt). Nh• vËy, bÊt kú ®iÓm biÕn ®æi trªn A lµ mét hµm tuyÕn tÝnh cña a, b, xt, vµ yt. 2.7. KÕt luËn. Ch•¬ng nµy tr×nh bµy c¸c vÊn ®Ò biÓu diÔn c¸c kh«ng gian cÊu h×nh vµ c¸c phÐp biÕn ®æi cña robot trong kh«ng gian ®Æc biÖt lµ kh«ng gian Cobs.§©y chÝnh lµ nh÷ng kiÕn thøc lµm nÒn t¶ng cho c¸c ph•¬ng ph¸p lËp lé tr×nh chÝnh x¸c. (2.40) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 48 Ch•¬ng III Mét sè ph•¬ng ph¸p chÝnh x¸c lËp lé tr×nh chuyÓn ®éng 3.1.Giíi thiÖu chung Trong vÊn ®Ò lËp tr×nh cho robot cã rÊt nhiÒu nh÷ng gi¶i thuËt lËp lé tr×nh, mçi gi¶i thuËt cã nh÷ng tiÒm n¨ng vµ øng dông nhÊt ®Þnh. C¸c ph•¬ng ph¸p cã thÓ bao gåm c¸c ph•¬ng ph¸p lÊy mÉu c¬ së, ph•¬ng ph¸p lËp lé tr×nh chÝnh x¸c. 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Ø. Nhê cã tÝnh chÊt nµy nªn c¸ch tiÕp cËn nµy cßn gäi lµ gi¶i thuËt lËp lé tr×nh chÝnh x¸c. Sù biÓu diÔn quan träng: Khi nghiªn cøu nh÷ng gi¶i thuËt nµy ®iÒu quan träng lµ viÖc xem xÐt cÈn thËn ®Þnh nghÜa ®Çu vµo : - M« h×nh nµo ®•îc sö dông ®Ó m« h×nh ho¸ robot vµ ch•íng ng¹i vËt? - TËp hîp nh÷ng biÕn ®æi nµo ®•îc ¸p dông cho Robot? - Sè chiÒu cña kh«ng gian? - Robot vµ kh«ng gian cã tho¶ m·n tÝnh chÊt låi kh«ng? - Chóng cã lµ ph©n ®o¹n tuyÕn tÝnh? ChØ ®Þnh râ c¸c ®Çu vµo cã thÓ x¸c ®Þnh tËp c¸c thÓ hiÖn cña bµi to¸n mµ trªn ®ã c¸c thuËt to¸n sÏ t¸c nghiÖp. NÕu nh÷ng thÓ hiÖn cã nh÷ng tÝnh chÊt thuËn lîi nhÊt ®Þnh (sè chiÒu cña kh«ng gian thÊp, nh÷ng m« h×nh thÓ hiÖn lµ kh«ng gian låi…) th× mét gi¶i thuËt tæ hîp cã thÓ cung cÊp mét gi¶i ph¸p rÊt tèt vµ thùc tÕ. NÕu tËp hîp cña nh÷ng thÓ hiÖn qu ¸ réng, th× mét yªu cÇu ph¶i tho¶ m·n c¶ tÝnh chÊt trän vÑn lÉn nh÷ng gi¶i ph¸p thùc hµnh cã thÓ v« lý, nh÷ng c«ng thøc chung cña vÊn ®Ò lËp lé tr×nh chuyÓn ®éng kh«ng thÓ ®¹t ®•îc. Tuy vËy, vÉn tån t¹i mét sè ®iÓm chung ®Ó Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 49 hoµn thµnh nh÷ng gi¶i thuËt lËp lé tr×nh chuyÓn ®éng. T¹i sao cÇn ph¶i nghiªn cøu ph•¬ng ph¸p lËp lé tr×nh tæ hîp? Cã hai lý do cÇn nghiªn cøu nh÷ng ph•¬ng ph¸p tæ hîp ®Ó tiÕp cËn tíi viÖc lËp lé tr×nh chuyÓn ®éng, ®ã lµ : Thø nhÊt, trong nhiÒu øng dông, viÖc lËp lé tr×nh chuyÓn ®éng cã thÓ chØ quan t©m ®Õn mét líp ®Æc biÖt, vÝ dô víi kh«ng gian chØ lµ kh«ng gian hai chiÒu 2D, vµ robot chØ cã kh¶ n¨ng tÞnh tiÕn. Khi tËp hîp nhiÒu líp ®Æc biÖt th× nh÷ng gi¶i thuËt thùc thi cã thÓ ®•îc ph¸t triÓn. Nh÷ng gi¶i thuËt nµy lµ ®Çy ®ñ, kh«ng phô thuéc vµo sù xÊp xØ, vµ tá ra thùc hiÖn tèt h¬n h¬n nh÷ng ph•¬ng ph¸p lËp lé tr×nh lÊy mÉu c¬ së. Thø hai, nh÷ng ph•¬ng ph¸p tæ hîp võa ®¸ng chó ý l¹i võa tho¶ m·n cho mét líp réng nh÷ng gi¶i thuËt lËp lé tr×nh chuyÓn ®éng. Tuy nhiªn, còng cÇn ph¶i chó ý víi ®a sè c¸c ph•¬ng ph¸p cã thÓ thùc th i, nh•ng ng•îc l¹i cßn mét sè gi¶i thuËt cßn qu ¸phøc t¹p vµ khã øng dông trong thùc tÕ. Dï mét gi¶i thuËt trong lý thuyÕt cho c¸c chi phÝ vÒ thêi gian thùc hiÖn rÊt nhá, nh•ng trong thùc tÕ khi thùc hiÖn th× nã khã cã thÓ ®¹t ®•îc møc chi phÝ ®ã. §«i khi ng•êi ta ph¶i chÊp nhËn tr•êng hîp nh÷ng gi¶i thuËt cã thêi gian ch¹y xÊu h¬n nhiÒu so víi gi¶i thuËt lý thuyÕt nh•ng l¹i dÔ hiÓu vµ dÔ thùc hiÖn h¬n. §©y còng vÉn lµ mét vÊn ®Ò më ®Ó nh÷ng ng•êi lËp tr×nh cÇn cè g¾ng x©y dùng nh÷ng gi¶i thuËt ngµy cµng hiÖu qu¶ h¬n cho dï hiÖn nay kÕt qu¶ chñ yÕu vÉn lµ trªn lý thuyÕt. V× vËy nã lu«n thóc ®Èy mäi ng•êi t×m kiÕm nh÷ng gi¶i thuËt ®¬n gi¶n vµ hiÖu qu¶ h¬n trong thùc tÕ. Roadmaps HÇu nh• tÊt c¶ c¸ch tiÕp cËn cña viÖc lËp lé tr×nh chÝnh x¸c lµ x©y dùng mét ®•êng ®i theo mét c¸ch nµo ®ã ®Ó gi¶i quyÕt nh÷ng truy vÊn. Kh¸i niÖm nµy ®· ®•îc giíi thiÖu. Nh•ng trong ch•¬ng nµy yªu cÇu Roadmaps ph¶i ®•îc ®Þnh nghÜa chÝnh x¸c h¬n bëi v× c¸c gi¶i thuËt ë ®©y cÇn x©y dùng trän vÑn. Mét sè gi¶i thuËt lËp lé tr×nh tæ hîp ®•îc tiÕp cËn theo ý t•ëng tr•íc hÕt x©y dùng mét sù ph©n ly Cfree vµ tõ ®ã sÏ x©y dùng lªn ®•êng ®i. Mét sè ph•¬ng ph¸p kh¸c l¹i trùc tiÕp x©y dùng mét Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 50 ®•êng ®i mµ kh«ng xem xÐt ®Õn sù ph©n ly «. §Þnh nghÜa Roadmap: Cho G lµ mét ®å thÞ t«p« ¸nh x¹ vµo trong Cfree. L¸t c¾t S Cfree lµ tËp hîp cña tÊt c¶ c¸c ®iÓm trong tÇm víi bëi G, (S= )]1,0([ £ e e  trong ®ã e([0,1]) Cfree lµ ¶nh cña ®•êng ®i e). §å thÞ G ®•îc gäi mét Roadmap nÕu nã tháa m·n hai ®iÒu kiÖn quan träng sau: 1. TÝnh dÔ tiÕp cËn : Tõ bÊt kú q Cfree, ph¶i tÝnh to¸n ®•îc mét ®•êng ®i hiÖu qu¶ vµ ®¬n gi¶n : [ 0, 1 ] Cfree sao cho (0) = q vµ (1) = s, trong ®ã s lµ mét ®iÓm bÊt kú trong S. Th«ng th•êng, s lµ ®iÓm gÇn nhÊt víi q, víi gi¶ thiÕt C lµ mét kh«ng gian metric. 2. Duy tr× kÕt nèi : Thø nhÊt, lu«n lu«n cã thÓ nèi ®•îc qI vµ qG tíi mét vµi s1 vµ s2, theo thø tù trong S. Thø hai yªu cÇu r»ng nÕu tån t¹i mét ®•êng ®i :[0,1] Cfree sao cho (0) = qI vµ (1) = qG, th× ë ®ã còng tån t¹i mét ®•êng ®i ' : [0,1] S, mµ '(0) = s1 vµ '(1) = s2. Nh• vËy, nh÷ng gi¶i ph¸p kh«ng lçi bëi v× G lu«n gi÷ liªn kÕt víi Cfree. §iÒu nµy b¶o ®¶m r»ng ph¸t triÓn nh÷ng gi¶i thuËt hoµn chØnh. Khi tháa m·n nh÷ng thuéc tÝnh nµy, mét ®•êng ®i sÏ cung cÊp mét sù biÓu diÔn rêi r¹c cho vÊn ®Ò lËp lé tr×nh chuyÓn ®éng. Mét truy vÊn, (qI, qG), ®•îc gi¶i quyÕt bëi viÖc nèi mçi truy vÊn ®iÓm cho Roadmap vµ sau ®ã biÓu diÔn mét sù t×m kiÕm ®å thÞ rêi r¹c trªn G. Duy tr× tÝnh chÊt ®Çy ®ñ, lµ ®iÒu kiÖn ®Çu tiªn b¶o ®¶m r»ng bÊt kú truy vÊn nµo ®Òu cã thÓ ®•îc nèi tíi G, vµ ®iÒu kiÖn thø hai b¶o ®¶m r»ng sù t×m kiÕm lu«n lu«n tiÕp nèi nÕu tån t¹i mét gi¶i ph¸p. 3.2. BiÓu diÔn kh«ng gian ch•íng ng¹i vËt Tr•íc khi nghiªn cøu mÉu chung nhÊt cña vÊn ®Ò lËp lé tr×nh tæ hîp, chóng ta nªn tiÕp cËn nh÷ng tr•êng hîp ®¬n gi¶n vµ trùc quan víi nh÷ng gi¶i thuËt minh b¹ch cho tr•êng hîp C = R2 vµ Cobs lµ ®a gi¸c. HÇu hÕt nh÷ng ®iÒu ®ã kh«ng thÓ trùc tiÕp ®•îc më réng tíi nh÷ng kh«ng gian cã sè chiÒu cao h¬n nh•ng nh÷ng nguyªn lý chung vÉn t•¬ng tù; Bëi vËy, rÊt cÇn thiÕt ®Ó tiÕp cËn viÖc lËp lé tr×nh chuyÓn ®éng chÝnh x¸c trong kh«ng gian hai chiÒu. Cã mét vµi øng dông cña nh÷ng gi¶i thuËt nµy cã thÓ trùc tiÕp ¸p dông. Mét vÝ dô cho viÖc lËp lé tr ×nh nhá cho mét Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 51 Robot di ®éng cã thÓ ®•îc m« h×nh nh• mét ®iÓm di ®éng trong mét toµ nhµ mµ b¶n ®å sµn nhµ ®•îc m« h×nh b»ng mét ®a gi¸c 2D 3.2.1 BiÓu diÔn Gi¶ thiÕt : W = R2; Nh÷ng ch•íng ng¹i O lµ ®a gi¸c; Robot A lµ mét robot ®iÓm chØ cã kh¶ n¨ng tÞnh tiÕn. Gi¶ sö Cobs còng lµ ®a gi¸c, tr•êng hîp ®Æc biÖt A lµ mét ®iÓm trong W, nh÷ng ¸nh x¹ trùc tiÕp tõ O tíi Cobs kh«ng cã bÊt kú sù biÕn d¹ng nµo. Nh• vËy, nh÷ng vÊn ®Ò ë ®©y ®•îc xem xÐt nh• viÖc lËp lé tr×nh cho mét robot ®iÓm. NÕu A kh«ng lµ robot ®iÓm th× hiÖu Minkowski cña O vµ A ®•îc tÝnh to¸n. Víi tr•êng hîp c¶ hai A vµ O lµ låi, gi¶i thuËt m« h×nh Cobs râ rµng trong tr•- êng hîp tÞnh tiÕn cã thÓ ®•îc ¸p dông tÝnh to¸n mçi thµnh phÇn cña C obs. H×nh 3.1 : Mét m« h×nh kh«ng gian ®•îc chØ râ bëi bèn ®a gi¸c cã h•íng ®¬n gi¶n. Trong tr•êng hîp tæng qu¸t, c¶ hai A vµ O cã thÓ lµ kh«ng låi vµ thËm chÝ chóng cã thÓ chøa ®ùng nh÷ng lç, nh• nh÷ng Cobs trong h×nh 3.1. Trong tr•êng hîp nµy, A vµ O ®•îc ph©n ly vµo trong nh÷ng thµnh phÇn låi, vµ hiÖu Minkowski ®•îc sö dông ®Ó tÝnh to¸n cho mçi cÆp cña nh÷ng thµnh phÇn. Mçi lÇn hiÖu Minkowski ®•îc tÝnh to¸n, chóng cÇn hîp nhÊt ®Ó thu ®•îc mét c¸ch biÓu diÔn d•íi d¹ng nh÷ng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 52 ®a gi¸c ®¬n gi¶n, nh• nh÷ng ®a gi¸c trong H×nh 3.1. Thùc thi c¸c gi¶i thuËt trong phÇn nµy sÏ gióp chóng ta sö dông mét cÊu tróc d÷ liÖu cho phÐp truy cËp thuËn tiÖn vµo c¸c th«ng tin trong m« h×nh . §Ó biÓu diÔn ®•îc chóng ta cÇn ph¶i tr¶ lêi ®•îc nh÷ng c©u hái: - BiÓu diÔn ®•êng biªn ngoµi nh• thÕ nµo? - Nh÷ng lç ë trong nh÷ng ch•íng ng¹i ®•îc biÓu diÔn ra sao? - Lµm thÕ nµo chóng ta biÕt nh÷ng lç nµo bªn trong nh÷ng ch•íng ng¹i vËt? Nh÷ng truy vÊn nµy cã thÓ ®•îc tr¶ lêi hiÖu qu¶ bëi viÖc sö dông cÊu tróc d÷ liÖu danh s¸ch liªn th«ng hai ®Çu. Chóng ta sÏ cÇn biÓu diÔn nh÷ng m« h×nh vµ mäi th«ng tin kh¸c cña nh÷ng gi¶i thuËt lËp lé tr×nh ®Ó duy tr× trong thêi gian thùc hiÖn. Cã ba b¶n ghi kh¸c nhau : §Ønh : Mçi ®Ønh v chøa ®ùng mét con trá tíi mét ®iÓm ( x, y) C = R2 vµ mét con trá tíi nöa –c¹nh nµo ®ã mµ v lµ gèc cña nã. MÆt : Mçi mÆt cã mét con trá tíi mét chu tr×nh nöa –c¹nh trªn biªn giíi bao quanh mÆt; gi¸ trÞ con trá lµ NIL nÕu mÆt lµ biªn giíi ë ngoµi cïng. MÆt còng chøa ®ùng mét danh s¸ch nh÷ng con trá cho mçi thµnh phÇn cã quan hÖ (nh• c¸c lç) chøa ®ùng ë trong mÆt ®ã. Nöa – c¹nh: Mçi Nöa –c¹nh ®•îc ®Þnh h•íng ®Ó phÇn ch•íng ng¹i lu«n lu«n ë bªn tr¸i nã. C¸c nöa c¹nh lu«n lu«n ®•îc xÕp trong nh÷ng chu tr×nh ®Ó h×nh thµnh ranh giíi cña mét mÆt. Nh÷ng chu tr×nh nh• vËy lu«n ®Þnh h•íng ®Ó phÇn ch•íng ng¹i vËt lu«n lu«n ë bªn tr¸i nã. Nã gi÷ mèi liªn hÖ víi nöa c¹nh tiÕp theo vµ nöa c¹nh tr•íc nã trong chu tr×nh. VÝ dô trong H×nh 3.1, cã bèn chu tr×nh cña nh÷ng nöa c¹nh mµ mçi chu tr×nh lµ giíi h¹n cña mét mÆt kh¸c nhau. C¸c nöa c¹nh lu«n theo mét h•íng nhÊt ®Þnh nªn nh÷ng chu tr×nh gianh giíi ngoµi cña nh÷ng ch•íng ng¹i vËt lu«n lu«n ch¹y ng•îc chiÒu kim ®ång hå (bªn tr¸i), vµ nh÷ng chu tr×nh ranh giíi cña lç trèng lu«n Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 53 theo chiÒu thuËn chiÒu kim ®ång hå. 3.3. Mét sè gi¶i thuËt lËp lé tr×nh chÝnh x¸c cho robot Cã rÊt nhiÒu gi¶i thuËt kh¸c lËp lé tr×nh chÝnh x¸c. ë ®©y chóng ta tËp chung vµo hai gi¶i thuËt lËp lé tr×nh chÝnh x¸c tiªu biÓu ®ã lµ Visibility Graph vµ Cell decomposition. 3.3.1 . Roadmap Visibility Graph – §å thÞ tÇm nh×n Víi môc ®Ých t×m thÊy nh÷ng ®•êng ®i ng¾n nhÊt cho robot ®· dÉn tíi ph•¬ng ph¸p Roadmap Visibility graph. ý t•ëng cña gi¶i thuËt nµy cã thÓ ®•îc coi lµ vÝ dô ®Çu tiªn cho mét gi¶i thuËt lËp lé tr×nh chuyÓn ®éng. Roadmap Visibility graph cho phÐp l•ít qua nh÷ng gãc cña Cobs. Trong thùc tÕ, ®©y lµ mét vÊn ®Ò ®•a ra t•¬ng ®èi khã bëi v× C free lµ mét tËp hîp më. Bëi v× víi bÊt kú ®•êng ®i nµo : [0,1] Cfree, lu«n lu«n cã thÓ ®Ó t×m thÊy mét ®•êng ng¾n h¬n. Do lý do nµy, chóng ta ph¶i xem xÐt vÊn ®Ò x¸c ®Þnh nh÷ng ®•êng ®i ng¾n nhÊt trong cl(Cfree) – tËp ®ãng cña Cfree. §iÒu nµy cã nghÜa r»ng robot ®•îc cho phÐp “ch¹m” hoÆc “ l­ít qua ” nh÷ng ch­íng ng¹i, nh•ng nã kh«ng ®•îc phÐp xuyªn qua chóng. Trªn thùc tÕ ng•êi ta tÝnh to¸n ®iÒu chØnh mét l•îng nhá cho ®•êng ®i gi¶i ph¸p cña lé tr×nh, ®Ó chóng cã thÓ ®Õn rÊt gÇn Cobs nh•ng kh«ng va vµo chóng. §iÒu nµy lµm t¨ng thªm ë møc ®é kh«ng ®¸ng kÓ ®é dµi ®•êng dÉn. L•îng bæ sung cã thÓ ®•îc lµm nhá tïy ý cho ®•êng ®i cã thÓ ®Õn gÇn Cobs tuú ý. 3.3.1.1. X©y dùng Roadmap Visibility Graph Gi¶ thiÕt r»ng tÊt c¶ ®Ønh cña mét ®a gi¸c låi kh«ng cã ba ®Ønh liªn tiÕp nµo céng tuyÕn lµ ®Ønh ph¶n x¹. §å thÞ G víi: C¸c ®Ønh lµ c¸c ®Ønh ph¶n x¹. Nh÷ng c¹nh cña G ®•îc h×nh thµnh tõ hai nguån kh¸c nhau : - §Ønh ph¶n x¹ liªn tiÕp : NÕu hai ®Ønh ph¶n x¹ lµ ®iÓm cuèi cña mét c¹nh cña Cobs, th× mét c¹nh gi÷a chóng ®•îc x©y dùng bªn trong G. - TiÕp tuyÕn c¹nh : NÕu mét ®•êng tiÕp tuyÕn cã thÓ ®•îc vÏ xuyªn qua mét Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 54 cÆp cña ®Ønh ph¶n x¹, th× mét c¹nh t•¬ng øng ®•îc x©y dùng bªn trong G. Mét ®•êng tiÕp tuyÕn, lµ mét ®•êng liªn quan tíi hai ®Ønh ph¶n x¹ cña Cobs vµ c¸c ®Ønh nµy ph¶i nh×n thÊy lÉn nhau. Mét vÝ dô cña roadmap kÕt qu¶ ®•îc cho thÊy trong H×nh 3.2. H×nh 3.2 : X©y dùng Roadmap Visibility Graph bao gåm c¸c c¹nh gi÷a ®Ønh ph¶n x¹ liªn tiÕp trªn Cobs vµ c¶ nh÷ng c¹nh tiÕp tuyÕn. H×nh 3. 3 : qI vµ qG ®•îc nèi tíi tÊt c¶ ®Ønh cã thÓ thÊy cña roadmap ®Ó t×m kiÕm ®•êng dÉn Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 55 3.3.1.2. Gi¶i ph¸p cho truy vÊn: qI vµ qG ®•îc nèi tíi tÊt c¶ ®Ønh roadmap mµ cã thÓ thÊy trong H×nh 3.3, chÝnh ®iÒu ®ã lµm cho roadmap më réng cã thÓ t×m kiÕm ®•îc mét gi¶i ph¸p. NÕu gi¶i thuËt cña Dijkstra ®•îc sö dông, vµ nÕu mçi c¹nh ®•îc ®•a vµo mét gi¸ trÞ t•- ¬ng øng th× gi¸ cña ®•êng ®i chÝnh lµ ®é dµi cña ®•êng ®i ®ã, ®•êng ®i kÕt qu¶ gi¶i ph¸p lµ ®•êng ®i ng¾n nhÊt gi÷a qI vµ qG. §•êng ®i ng¾n nhÊt cho vÝ dô trong H×nh 3.3 ®•îc cho thÊy trong H×nh 3.4. H×nh 3.4 : §•êng ®i ng¾n nhÊt trong Roadmap lµ ®•êng ®i ng¾n nhÊt gi÷a qI vµ qG. §¸nh gi¸ gi¶i thuËt: NÕu tiÕp tuyÕn kiÓm tra ®•îc thùc hiÖn ®¬n gi¶n, th× kÕt qu¶ gi¶i thuËt yªu cÇu thêi gian O(n3), trong ®ã n lµ sè ®Ønh cña Cobs. Cã O(n 2) nh÷ng cÆp cña ®Ønh ph¶n x¹ cÇn kiÓm tra, vµ mçi sù kiÓm tra yªu cÇu O(n) thêi gian kiÓm tra nhÊt ®Þnh ®Ó ®¶m b¶o r»ng kh«ng cã bê nµo kh¸c ng¨n chóng nh×n thÊy nhau. Nguyªn lý planesweep cã thÓ ®•îc lµm thÝch nghi ®Ó thu ®•îc mét gi¶i thuËt tèt h¬n víi thêi gian cÇn thiÕt chØ lµ O(n2lg n). ý t•ëng thùc hiÖn nguyªn lý planesweep : Dïng mét tia quay quÐt tõ mçi ®Ønh ph¶n x¹, v. Mét tia ®•îc khëi ®éng t¹i = 0, vµ nh÷ng sù kiÖn xuÊt hiÖn khi tia ch¹m ®Ønh. Mét tËp hîp cña tiÕp tuyÕn xuyªn qua v cã thÓ ®•îc tÝnh to¸n bªn trong theo c¸ch nµy trong thêi gian O(nlgn). Tõ ®ã cã O(n) ®Ønh ph¶n x¹, tæng thêi gian thùc hiÖn lµ O(n2lgn). Ta thÊy mét gi¶i thuËt cã thÓ tÝnh to¸n ®•êng dÉn ng¾n Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 56 nhÊt trong thêi gian O(nlgn + m), trong ®ã m lµ tæng sè c¹nh trong roadmap. NÕu vïng ch•íng ng¹i ®•îc m« t¶ bëi mét ®a gi¸c ®¬n gi¶n, th× sù nhãm thêi gian cã thÓ ®•îc gi¶m tíi O(n). 3.3.1.3. Ch•¬ng tr×nh thö nghiÖm vµ ®¸nh gi¸ a) Ch•¬ng tr×nh thö nghiÖm Ch•¬ng tr×nh ®•îc viÕt b»ng ng«n ng÷ Visual Basic (xem phô lôc 1) dùa theo s¬ ®å thuËt to¸n nh• (h×nh 3.5). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 57 - Nèi I víi J - CËp nhËt träng sè ts(i,j) = ts(j,i) X¸c ®Þnh c¸c ®a gi¸c vËt c¶n víi tæng sè n ®Ønh Ghi nhËn to¹ ®é ®Ønh cña c¸c vËt c¶n i=1 I<=n Begin J=1, Dk =False J <=n k=1 §o¹n [I,J] giao víi ®o¹n [K,K+1] T Dk:=true K=K +1 F K I = I+1 J = J+1 F T T F K <=n <=n Dk=False T T F ¸p dông Dijktra t×m ®•êng ®i ng¾n nhÊt End ChØ ra ®•êng dÉn tèi •u H×nh 3.5 S¬ ®å thuËt to¸n Visibility Graph Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 58 b-KÕt qu¶ ®¹t ®•îc: Ch•¬ng tr×nh cho phÐp ng•êi sö dông cã thÓ x©y dùng kh«ng gian tr¹ng th¸i bÊt kú. Trªn c¬ së ®ã x©y dùng ®å thÞ tÇm nh×n vµ t×m ®•îc ®•êng ®i tèi •u cho robot tõ qI ®Õn qG bÊt kú. Ch•¬ng tr×nh trªn ®· ®•îc thö nghiÖm víi mét sè kh«ng gian cÊu h×nh nh• sau: H×nh 3.6- Mét sè ®•êng ®i gi¶i ph¸p cña ch•¬ng tr×nh thùc nghiÖm gi¶i thuËt Visibility Graph Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 59 3.3.2. Vertical Cell Decomposition (ph©n ly ¤ däc ) Nh÷ng ph•¬ng ph¸p tæ hîp ph¶i x©y dùng mét cÊu tróc d÷ liÖu h÷u h¹n ®Ó m· ho¸ chÝnh x¸c vÊn ®Ò lËp lé tr×nh. Nh÷ng gi¶i thuËt ph©n ly « h•íng tíi viÖc chia c¾t Cfree thµnh mét tËp hîp h÷u h¹n nh÷ng vïng gäi lµ nh÷ng «. Sù ph©n ly « cÇn ph¶i tháa m·n ba thuéc tÝnh : 1.ViÖc x©y dùng mét ®•êng ®i tõ mét ®iÓm bªn trong mét « ph¶i dÔ dµng. VÝ dô, nÕu mçi « låi, th× bÊt kú cÆp ®iÓm nµo trong mét « ®Òu cã thÓ nèi ®•îc bëi mét ®o¹n th¼ng. 2. Sù cung cÊp th«ng tin cho nh÷ng « liÒn kÒ ph¶i dÔ dµng ®Ó x©y dùng roadmap. 3. Cho tr•íc mét qI vµ qG, sù ph©n ly « cÇn ph¶i x¸c ®Þnh ®•îc nh÷ng « nµo chøa chóng. NÕu mét sù ph©n ly « tháa m·n nh÷ng thuéc tÝnh nµy, th× vÊn ®Ò lËp lé tr×nh chuyÓn ®éng ®•îc biÕn ®æi thµnh vÊn ®Ò t×m kiÕm ®å thÞ. Tuy nhiªn, trong sù thiÕt ®Æt hiÖn thêi, toµn bé ®å thÞ, G, th«ng th•êng ®•îc biÕt tr•íc. §iÒu nµy kh«ng gi¶ thiÕt riªng cho nh÷ng vÊn ®Ò lËp lé tr×nh. 3.3.2.1. §Þnh nghÜa sù ph©n ly däc: PhÇn nµy chóng ta giíi thiÖu mét gi¶i thuËt mµ x©y dùng mét sù ph©n ly « däc. Cfree ®•îc ph©n chia vµo trong mét tËp hîp h÷u h¹n cña nh÷ng 2-cell vµ 1-cell. Mçi 2 - cell lµ mét h×nh thang cã nh÷ng c¹nh däc hoÆc lµ mét h×nh tam gi¸c (lµ mét h×nh thang suy biÕn). Víi lý do nµy, ph•¬ng ph¸p nµy cßn ®•îc gäi sù ph©n ly h×nh thang. Sù ph©n ly ®•îc ®Þnh nghÜa nh• sau: Cho P biÓu thÞ tËp hîp cña ®Ønh ®Þnh nghÜa Cobs. T¹i mçi p P, dïng nh÷ng tia th¼ng h•íng h•íng lªn hoÆc xuèng xuyªn qua Cfree, cho ®Õn khi va ph¶i Cobs th× dõng l¹i. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 60 H×nh 3.7 : Bèn tr•êng hîp tæng qu¸t cña tia ph©n ly: 1) Cã thÓ theo hai h•íng xuèng xu«i hoÆc h•íng lªn, 2) ChØ h•íng lªn, 3) ChØ xu«i xuèng, vµ 4) Kh«ng thÓ më réng. 1. Khi ph©n ly sÏ cã bèn tr•êng hîp, nh• trong H×nh 3.7, phô thuéc vµo lµ nã cã thÓ ®Ó më réng theo hai ph•¬ng h•íng hay kh«ng. NÕu C free ®•îc ph©n chia theo nh÷ng tia nµy, th× kÕt qu¶ lµ mét sù ph©n ly däc. VÝ dô víi C obs trong H×nh 3.7 a sö dông sù ph©n ly däc Cfree ta ®•îc h×nh H×nh 3.7 b. H×nh 3.8 : Sö dông ph•¬ng ph¸p ph©n ly « däc ®Ó x©y dùng mét roadmap, ®•îc t×m kiÕm ®Ó sinh ra mét gi¶i ph¸p cho mét truy vÊn. Chó ý r»ng chØ nh÷ng h×nh thang vµ nh÷ng h×nh tam gi¸c thu ®•îc gäi lµ nh÷ng 2 - cell trong Cfree. Mçi 1-cell lµ mét ®o¹n däc ®¸p øng nh• mét c¹nh gi÷a hai 2 - cell. Khi ph©n ly chóng ph¶i b¶o ®¶m r»ng topology cña Cfree ®•îc biÓu diÔn chÝnh x¸c. Ta ®· biÕt r»ng Cfree ®· ®•îc ®Þnh nghÜa lµ mét tËp hîp më. Mçi 2- cell thËt sù còng ®•îc ®Þnh nghÜa lµ mét tËp hîp më trong R2; nh• vËy, nã lµ phÇn trong cña mét h×nh thang hoÆc h×nh tam gi¸c vµ 1- cell lµ nh÷ng ®iÓm trªn c¸c ®o¹n th¼ng. 3.3.2.2 §Þnh nghÜa roadmap trong ph•¬ng ph¸p §Ó ®iÒu khiÓn nh÷ng truy vÊn lËp lé tr×nh chuyÓn ®éng, mét roadmap ®•îc Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 61 x©y dùng tõ sù ph©n ly däc. Cho mçi « Ci, gäi qi lµ mét ®Ønh sao cho qi Ci khi ®ã qi ®•îc gäi lµ ®iÓm mÉu. Nh÷ng ®iÓm mÉu cã thÓ ®•îc lùa chän theo nhiÒu c¸ch, vÝ dô nh• nh÷ng träng t©m trong c¸c «, nh•ng sù lùa chän ®Æc biÖt kh«ng ph¶i lµ qu¸ quan träng, cã thÓ tån t¹i nhiÒu c¸ch lùa chän ®iÓm mÉu kh¸c. H×nh 3.9 : Roadmap b¾t nguån tõ sù ph©n ly « däc. Cho G(V,E) lµ mét ®å thÞ t«p« ®Þnh nghÜa nh• sau: Víi mçi «, Ci, ®Þnh nghÜa mét ®Ønh qi V. Víi mçi 2- cell, ®Þnh nghÜa mét c¹nh tõ ®iÓm mÉu ®· lùa chän cña nã ®Õn ®iÓm mÉu ®· lùa chän cña mçi 1- cell n»m däc theo ranh giíi cña nã. Mçi c¹nh lµ mét ®o¹n th¼ng nèi gi÷a c¸c ®iÓm lùa chän cña c¸c «. §å thÞ kÕt qu¶ lµ mét roadmap (H×nh 3.9). §iÒu kiÖn dÔ tiÕp cËn ®•îc tháa m·n bëi v× mçi ®iÓm mÉu cã thÓ ®¹t ®•îc bëi mét ®•êng ®i nhê vµo tÝnh låi cña mçi «. §iÒu kiÖn kÕt nèi còng ®•îc tháa m·n v× G nhËn ®•îc tõ sù ph©n ly «, mµ khi ph©n ly vÉn gi÷ quan hÖ thuéc Cfree. Mçi lÇn roadmap x©y dùng xong, c¸c th«ng tin vÒ « kh«ng cÇn ®•îc l•u gi÷ n÷a. §èi víi viÖc tr¶ lêi cho nh÷ng truy vÊn lËp lé tr×nh chÝnh lµ roadmap ®· x©y dùng. 3.3.2.3. T×m lêi gi¶i cho mét truy vÊn Mét lÇn roadmap thu ®•îc, nã cã thÓ tr¶ lêi râ rµng cho mét truy vÊn cña vÊn ®Ò lËp lé tr×nh chuyÓn ®éng tõ qI ®Õn qG. Cho C0 vµ Ck biÓu thÞ nh÷ng « chøa ®ùng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 62 qI vµ qG t•¬ng øng. Trong ®å thÞ G, t×m kiÕm mét ®•êng ®i cã thÓ nèi tõ ®iÓm mÉu cña C0 tíi ®iÓm mÉu cña Ck. NÕu kh«ng cã ®•êng ®i nh• vËy nµo tån t¹i, th× gi¶i thuËt tuyªn bè kh«ng tån t¹i gi¶i ph¸p. NÕu tån t¹i mét ®•êng ®i th× cho C1, C2, . . ., Ck-1 lÇn l•ît ®i qua tÊt c¶ nh÷ng ®iÓm mÉu cña c¸c 1 - cell vµ 2- cell tõ C0 ®Õn Ck. Mét ®•êng ®i gi¶i ph¸p cã thÓ ®•îc h×nh thµnh mét c¸ch ®¬n gi¶n b»ng c¸ch “Nèi nh÷ng ®iÓm”, q0, q1, q2, . . ., qk-1, qk biÓu thÞ nh÷ng ®iÓm mÉu däc theo ®•êng ®i bªn trong G. §•êng ®i gi¶i ph¸p, : [ 0, 1 ] Cfree, ®•îc h×nh thµnh bëi viÖc ®Æt (0) = qI, (1) = qG, vµ viÖc ®Õn th¨m mçi ®iÓm trong d·y c¸c ®iÓm tõ q0 ®Õn qk ®i theo mét ®•êng ®i ng¾n nhÊt. VÝ dô, Gi¶i ph¸p trong H×nh 3.10. Trong viÖc lùa chän nh÷ng ®iÓm mÉu, ®iÒu ®ã quan träng ®Ó b¶o ®¶m r»ng mçi ®o¹n ®•êng ®i tõ ®iÓm mÉu cña mét « ®Õn ®iÓm mÉu cña nh÷ng « l¸ng giÒng cña nã kh«ng cã va ch¹m x¶y ra. H×nh 3.10 : VÝ dô mét ®•êng ®i gi¶i ph¸p 3.3.2.4. §¸nh gi¸ gi¶i thuËt: HiÖu qu¶ tÝnh to¸n sù ph©n ly sÏ ®•îc xem xÐt. Thùc chÊt trong vÊn ®Ò nµy c¸c b•íc ®Òu ®¬n gi¶n vµ thùc hiÖn bëi ph•¬ng ph¸p brute - force (b¾t Ðp th« b¹o) . NÕu Cobs cã n ®Ønh, th× c¸ch tiÕp cËn nµy cÇn Ýt nhÊt thêi gian lµ O(n2) v× ph¶i kiÓm tra sù giao nhau gi÷a mçi tia däc vµ mçi ®o¹n . NÕu tæ chøc cÈn thËn c¸c b•íc tÝnh to¸n th× kÕt qu¶ ch¹y thêi gian chØ cßn lµ O(nlgn). 3.3.2.5. Nguyªn lý quÐt mÆt ph¼ng: C¬ së cña gi¶i thuËt lµ nguyªn lý mÆt- quÐt (hoÆc ®•êng - quÐt) tõ mÉu h×nh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 63 häc trªn m¸y tÝnh, ®©y còng lµ c¬ së cña nhiÒu gi¶i thuËt lËp lé tr×nh tæ hîp vµ nhiÒu gi¶i thuËt chung kh¸c. NhiÒu vÊn ®Ò h×nh häc tÝnh to¸n bëi m¸y tÝnh cã thÓ ®•îc xem xÐt nh• sù ph¸t triÓn cña nh÷ng cÊu tróc d÷ liÖu vµ gi¶i thuËt mµ kh¸i qu¸t hãa ph©n lo¹i vÊn ®Ò cho nhiÒu chiÒu. Nãi c¸ch kh¸c, nh÷ng gi¶i thuËt cÈn thËn “ s¾p xÕp ” c¸c th«ng tin h×nh häc. Tõ “QuÐt” ®­îc sö dông khi tr×nh bµy nh÷ng gi¶ i thuËt nµy v× cã thÓ h×nh dung ®ã lµ mét ®•êng (hoÆc mÆt ph¼ng) quÐt ngang qua kh«ng gian, chØ dõng khi ®¹t ®Õn tr¹ng th¸i thay ®æi nµo ®ã khi t×m thÊy th«ng tin. Trªn ®©y míi lµ sù miªu t¶ trùc quan, cßn viÖc quÐt ch•a ®•îc biÓu diÔn râ rµng b»ng gi¶i thuËt. §Ó x©y dùng sù ph©n ly däc, h×nh d¹ng mét ®•êng däc lµ ®•êng quÐt tõ x = - tíi x = , gi¶ sö (x, y) lµ mét ®iÓm trong C = R2. D÷ liÖu ®Çu vµo lµ tËp hîp P cña ®Ønh Cobs. Bëi vËy chóng ta chØ quan t©m ®Õn nh÷ng vÊn ®Ò xuÊt hiÖn ë nh÷ng ®iÓm nµy. S¾p xÕp nh÷ng ®iÓm trong P theo thø tù to¹ ®é x t¨ng dÇn. Gi¶ thiÕt th«ng th•êng kh«ng cã hai ®iÓm nµo cã cïng täa ®é x. Nh÷ng ®iÓm trong P b©y giê sÏ ®•îc th¨m theo thø tù ®· s¾p xÕp. Mçi lÇn th¨m mét ®iÓm sÏ ®•îc coi lµ mét sù kiÖn. Tr•íc, sau, vµ gi÷a mçi sù kiÖn, mét danh s¸ch L chøa mét vµi c¹nh Cobs sÏ ®•îc x¸c nhËn. Danh s¸ch nµy ph¶i ®•îc duy tr× trong suèt thêi gian theo thø tù nh÷ng c¹nh ®Õn khi nµo va ph¶i ®•êng quÐt däc. Danh s¸ch ®•îc s¾p xÕp theo thø tù t¨ng dÇn. H×nh 3.11 : VÝ dô cã 14 sù kiÖn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 64 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. Nh÷ng b•íc thùc hiÖn gi¶i thuËt H×nh 3.11 vµ 3.12 thÓ hiÖn sù tr×nh diÔn gi¶i thuËt. §Çu tiªn, L trèng rçng, sau ®ã víi mçi sù kiÖn sÏ ®•a vµo danh s¸ch nh÷ng c¹nh biÓu diÔn cña Cfree cã liªn quan ®Õn sù kiÖn. Mçi thµnh phÇn liªn quan cña C free sinh ra mét phÇn tö ®¬n trong cÊu tróc d÷ liÖu. Sau vµi b•íc lÆp ta x©y dùng ®•îc L chÝnh x¸c. Mçi sù kiÖn sÏ xuÊt hiÖn lµ mét trong sè bèn tr•êng hîp trong H×nh 3.7. ViÖc duy tr× L trong mét c©y t×m nhÞ ph©n c©n ®èi, cã thÓ ®•îc x¸c ®Þnh trong thêi gian O(lg n), tèt h¬n rÊt nhiÒu so víi thêi gian O(n) cña tr•êng hîp b¾t buéc ph¶i kiÓm tra mäi ®o¹n. ViÖc phô thuéc vµo bèn tr•êng hîp xuÊt hiÖn tõ H×nh 3.7, dÉn tíi nh•ng cËp nhËt kh¸c nhau cña L ®•îc thùc hiÖn. NÕu tr•êng hîp xuÊt hiÖn ®Çu tiªn, th× hai c¹nh kh¸c nhau ®•îc chÌn vµo, vµ thÓ hiÖn ®ã trªn p lµ hai nöa ®o¹n. Hai tr•êng hîp tiÕp theo trong H×nh 3.7 th× ®¬n gi¶n h¬n; chØ mét thÓ hiÖn ®¬n ®•îc thùc hiÖn.Tr•êng hîp cuèi cïng, kh«ng xuÊt hiÖn viÖc ph©n ly. Mét lÇn thùc hiÖn thao t¸c ph©n ly bÒ mÆt cña Cfree th× L ®•îc cËp nhËt. Khi tia quÐt qua p, lu«n lu«n cã hai c¹nh bÞ ¶nh h•ëng. VÝ dô, trong tr•êng hîp ®Çu tiªn vµ cuèi cïng cña H×nh 3.7, hai c¹nh ph¶i ®•îc chÌn vµo trong L (¶nh ®èi xøng cña nh÷ng tr•êng hîp nµy lµ nguyªn nh©n hai c¹nh sÏ ®•îc xãa ®i tõ L). NÕu hai tr•êng hîp gi÷a xuÊt hiÖn, th× mét c¹nh ®•îc thay thÕ bëi ®èi t•îng kh¸c trong L. Nh÷ng thao t¸c thªm vµo vµ xãa ®i nµy cã thÓ ®•îc thùc hiÖn trong thêi gian O(lgn). Tõ ®ã khi cã sù kiÖn n, thêi gian cho x©y dùng gi¶i thuËt lµ O(nlgn). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 65 3.3.2.6. Ch•¬ng tr×nh thö nghiÖm Ch•¬ng tr×nh ®•îc viÕt b»ng ng«n ng÷ Visual Basic (xem phô lôc 2) dùa theo s¬ ®å thuËt to¸n nh• (h×nh 3.13). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 66 X¸c ®Þnh c¸c ®a gi¸c vËt c¶n víi tæng sè n ®Ønh Ghi nhËn to¹ ®é ®Ønh cña vËt c¶n A[i,j] Ph©n ly Cfree tia däc t¹i ®Ønh I X¸c ®Þnh ®iÓm mÉu X©y dùng Roadmap theo c¸c ®iÓm mÉu TÝnh to¸n vµ cËp nhËt ma trËn träng sè cña Roadmap T×m ®•êng ®i gi¶i ph¸p tõ qI ®Õn qG Begin End S¾p xÕp to¹ ®é c¸c ®iÓm mÉu theo thø tù t¨ng dÇn I=1 I<=n DK=True J <=n ®o¹n [J,J+1] giao víi tia däc qua I J =1 , DK=False DK=False J=J+1 T T F I=I+1 F H×nh 3.13 S¬ ®å thuËt to¸n Cell decomposition Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 67 KÕt qu¶ ®¹t ®•îc: Ch•¬ng tr×nh còng ®¸p øng ®•îc cho kh«ng gian tr¹ng th¸i bÊt kú víi ®Ých vµ nguån bÊt kú. VÝ dô: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 68 H×nh 3.14- Mét sè ®•êng ®i gi¶i ph¸p cña ch•¬ng tr×nh thùc nghiÖm gi¶i thuËt Cell Decompsition KÕt luËn Trong luËn v¨n " Mét sè ph•¬ng ph¸p chÝnh x¸c lËp lé tr×nh lËp lé tr×nh chuyÓn ®éng cho Robot " em ®· thùc hiÖn ®•îc mét sè c«ng viÖc sau: 1. §· tr×nh bµy ®•îc tæng quan cña bµi to¸n lËp lé tr×nh chuyÓn ®éng cho robot vµ c¸c øng dông cña bµi to¸n trong thùc tÕ. 2. Kh¸i qu¸t ®•îc c¬ së to¸n häc ®Ó biÓu diÔn kh«ng gian cÊu h×nh cña bµi to¸n cho c¸c gi¶i thuËt lËp lé tr×nh cho Robot . 3. §i s©u nghiªn cøu hai ph•¬ng ph¸p chÝnh x¸c lËp lé tr×nh chuyÓn ®éng cho Robot ®ã lµ Rodmap Visibility Graph vµ Vertical Cell Decomposition. Cµi ®Æt thùc nghiÖm thµnh c«ng hai ph•¬ng ph¸p trªn víi kh«ng gian tr¹ng th¸i bÊt kú vµ t×m ®•îc ®•êng ®i tèi •u cho Robot. 4. H•íng më réng cña ®Ò tµi nµy lµ tiÕp tôc më réng nghiªn cøu ¸p dông cho c¸c ph•¬ng ph¸p lËp lé tr×nh chÝnh x¸c trªn vµ mét sè c¸c ph•¬ng ph¸p kh¸c nh• Vonoroi Diagram hay Cylindrical Algebraic Decomposition trong c¸c kh«ng gian tr¹ng th¸i cã sè chiÒu lín h¬n. Më réng bµi to¸n sang c¸c ph­¬ng ph¸p lÊy mÉu c¬ së…. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 69 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 70 TÀI LIÖU THAM KH¶O 1. A. Abrams and R. Ghrist(2002), Finding topology in a factory: Configuration spaces. The American Mathematics Monthly. 2. B. Aronov and M. Sharir(December-1997). On translational motion planning of a convex polyhedron in 3-space. SIAM Journal on Computing. 3. G. Dudek, M. Jenkin (2000), Computational Principles of Mobile Robots , MIT Press. 4. J.C. Latombe (1991), Robot Motion Planning, Kluwer Academic Publishers. 5. J. Angeles. Spatial Kinematic Chains (1982). Analysis, Synthesis, and Optimisation. Springer-Verlag, Berlin. 6. J. F. Canny (1988). The Complexity of Robot Motion Planning. MIT Press, Cambridge, MA. 7. M. A. Armstrong (1983). Basic Topology. Springer-Verlag, New York. 8. P. K. Agarwal, B. Aronov, and M. Sharir (1999). Motion planning for a convex polygon in a polygonal environment. Discrete and Computational Geometry. 9. Steven M. LaValle (2006), Planning algorithms, Cambridge University Press, 842 pages. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 71 Phô lôc 1 Ch•¬ng tr×nh ph•¬ng ph¸p visibility Graph Option Explicit Dim dx, dy, a, b, c, i, j, n, k, k1, k2, s, t, u, v, di, ddx, ddy, dcx, dcy As Integer Dim maxint, minp As Single Dim ts(1 To 50, 1 To 50) As Single Dim truoc(1 To 50), d(1 To 50) As Single Dim final(1 To 50) As Boolean Dim Ar(1 To 50), Br(1 To 50), dc(1 To 10) As Integer Dim x1, x2, y1, y2, xp1, xp2, yp1, yp2, xc, yc As Integer Dim dk, dk1 As Boolean --------------------------------------------------------------------------------------------------- Private Sub Command1_Click() For i = 1 To n For j = 1 To n ts(i, j) = maxint Next j Next i For s = 2 To t For i = 1 To n For j = 1 To n dk = False 'Loai truong hop hai diem cung da giac If (j i + 1) And (i <= dc(s)) And (j <= dc(s)) Then dk = True End If If (j i + 1) And (i >= dc(s)) And (j >= dc(s)) Then dk = True End If 'C¸c truong hop khac For k = 1 To n - 3 If (i j) Then x1 = Ar(j) - Ar(i) y1 = Br(j) - Br(i) x2 = Ar(k + 1) - Ar(k) y2 = Br(k + 1) - Br(k) If ((y1 * Ar(k) - x1 * Br(k) - Ar(i) * y1 + Br(i) * x1) * (y1 * Ar(k + 1) - x1 * Br(k + 1) - Ar(i) * y1 + Br(i) * x1) < 0) And ((y2 * Ar(i) - x2 * Br(i) - Ar(k) * y2 + x2 * Br(k)) * (y2 * Ar(j) - x2 * Br(j) - Ar(k) * y2 + x2 * Br(k)) < 0) Then dk = True End If 'Lo¹i tr•êng hîp ®iÓm cuèi mçi ®a gi¸c k1 = dc(s - 1) + 1 k2 = dc(s) + 1 x2 = Ar(k2) - Ar(k1) y2 = Br(k2) - Br(k1) If ((y1 * Ar(k1) - x1 * Br(k1) - Ar(i) * y1 + Br(i) * x1) * (y1 * Ar(k2) - x1 * Br(k2) - Ar(i) * y1 + Br(i) * x1) < 0) And ((y2 * Ar(i) - x2 * Br(i) - Ar(k1) * y2 + x2 * Br(k1)) * (y2 * Ar(j) - x2 * Br(j) - Ar(k1) * y2 + x2 * Br(k1)) < 0) Then dk = True End If Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 72 End If Next k If dk = False And (Ar(j) 0) And (Ar(i) 0) Then DrawWidth = 2 Line (Ar(i), Br(i))-(Ar(j), Br(j)), &H800080 ts(i, j) = Sqr((Ar(j) - Ar(i)) * (Ar(j) - Ar(i)) + (Br(j) - Br(i)) * (Br(j) - Br(i))) ts(j, i) = Sqr((Ar(j) - Ar(i)) * (Ar(j) - Ar(i)) + (Br(j) - Br(i)) * (Br(j) - Br(i))) End If Next j Next i Next s End Sub ------------------------------------------------------------------------------------------- Private Sub Command3_Click() 'duong di ngan nhat s = n - 1 t = n ' Khoi tao For v = 1 To n d(v) = ts(s, v) truoc(v) = s final(v) = False Next v truoc(s) = 0 d(s) = 0 final(s) = True Do While Not (final(t)) minp = maxint For v = 1 To n If (Not (final(v))) And (minp > d(v)) Then u = v minp = d(v) End If Next v final(u) = True If Not (final(t)) Then For v = 1 To n If (Not (final(v))) And (d(u) + ts(u, v) < d(v)) Then d(v) = d(u) + ts(u, v) truoc(v) = u End If Next v End If Loop DrawWidth = 4 i = truoc(t) Line (Ar(t), Br(t))-(Ar(i), Br(i)), &HFF& Do While i s Line (Ar(i), Br(i))-(Ar(truoc(i)), Br(truoc(i))), &HFF& i = truoc(i) Loop End Sub Private Sub Form_Load() maxint = 1000000 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 73 n = 1 t = 1 di = 1 dc(1) = 0 End Sub ------------------------------------------------------------------------------------------------------------- Private Sub Form_MouseDown(Button As Integer, Shift As Integer, X As Single, Y As Single) If O2.Value = True Then Select Case Button Case vbLeftButton If c 2 Then Circle (X, Y), 30 a = X b = Y c = 2 dx = a dy = b Ar(n) = a Br(n) = b Else n = n + 1 Circle (X, Y), 30 DrawWidth = 6 Line (a, b)-(X, Y), QBColor(2) a = X b = Y Ar(n) = a Br(n) = b End If Case vbRightButton c = 1 DrawWidth = 6 Line (dx, dy)-(a, b), QBColor(2) n = n + 1 Ar(n) = dx Br(n) = dy t = t + 1 dc(t) = n n = n + 1 End Select Else If O1.Value = True Then Select Case Button Case vbLeftButton Circle (ddx, ddy), 30, &H8000000F Circle (X, Y), 30, QBColor(3) ddx = X ddy = Y Print "qI" Ar(n) = ddx Br(n) = ddy Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 74 n = n + 1 Case vbRightButton Circle (dcx, dcy), 30, &H8000000F Circle (X, Y), 30, QBColor(4) dcx = X dcy = Y Print "qG" Ar(n) = dcx Br(n) = dcy End Select Else MsgBox " Hay chon nut..." End If End If End Sub Phô lôc 2 Ch•¬ng tr×nh ph•¬ng ph¸p Cell Decompsition Option Explicit Dim dx, dy, a, b, c, i, j, n, k, k1, k2, s, t, u, v, td1, td2, qI, qG As Integer Dim maxint, minp, tgx, tgy, tg1, tg2, ddx, ddy, dcx, dcy, tdy1max, tdy2min, tdxmax, tdxmin As Single Dim tsxmax(1 To 5), tsymax(1 To 5), tsxmin(1 To 5), tsymin(1 To 5), dn1(1 To 5), dn2(1 To 5) As Single Dim ts(1 To 60, 1 To 60) As Single Dim truoc(1 To 60), d(1 To 60), dinh(1 To 60) As Single Dim final(1 To 50) As Boolean Dim Ar(1 To 60), Br(1 To 60), dc(1 To 10) As Single Dim x1, x2, y1, y2, xp1, xp2, yp1, yp2, xc, yc As Integer Dim tdx1(1 To 60), tdy1(1 To 60), tdx2(1 To 60), tdy2(1 To 60) As Single Dim dk, dk1 As Boolean ----------------------------------------------------------------------------------------------------------------------- - Private Sub Command1_Click() ' phan ly DrawWidth = 2 n = n - 1 For s = 2 To t For i = 1 To n dk = False For j = 1 To n - 1 If (j dc(s)) Then If ((Ar(j) - Ar(i)) * (Ar(j + 1) - Ar(i)) Br(j)) Or (Br(i) > Br(j + 1))) Then dk = True dk1 = True End If End If Next j If dk1 = False Then 'loai truong hop canh noi giua hai da giac k1 = dc(s - 1) + 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 75 k2 = dc(s) + 1 If ((Ar(k2) - Ar(i)) * (Ar(k1) - Ar(i)) Br(k2)) Or (Br(i) > Br(k1))) Then dk = False End If End If If (i 1) And (i n) And (dk = False) Then 'Phan ly va cap nhat ma tran trung diem 1 DrawWidth = 1 Line (Ar(i), Br(i))-(Ar(i), 0) tdx1(td1) = Ar(i) tdy1(td1) = Br(i) / 2 td1 = td1 + 1 End If Next i Next s Line (tdx1(1) - 300, 0)-(tdx1(1) - 300, 7000) 'phan ly ngoai vung da giac tdxmin = tdx1(1) - 300 tdx1(td1) = tdxmin tdy1(td1) = 7000 / 2 td1 = td1 + 1 '************************************** For i = 1 To n dk = False dk1 = False For j = 1 To n - 1 If (j dc(s)) Then If ((Ar(j) - Ar(i)) * (Ar(j + 1) - Ar(i)) < 0) And ((Br(i) < Br(j)) Or (Br(i) < Br(j + 1))) Then dk = True dk1 = True End If End If Next j If dk1 = False Then 'loai truong hop canh noi giua hai da giac k1 = dc(s - 1) + 1 k2 = dc(s) + 1 If ((Ar(k2) - Ar(i)) * (Ar(k1) - Ar(i)) Br(k2)) Or (Br(i) > Br(k1))) Then dk = False End If End If If (i 1) And (i n) And (dk = False) Then 'Phan ly va cap nhat ma tran trung diem 2 DrawWidth = 1 Line (Ar(i), Br(i))-(Ar(i), 7000) tdx2(td2) = Ar(i) tdy2(td2) = Br(i) + (7000 - Br(i)) / 2 td2 = td2 + 1 End If Next i td1 = td1 - 1'Sap xep mang td1 va tim tung do lon nhat tdy1max = tdy1(2) For i = 3 To td1 If tdy1(i) > tdy1max Then tdy1max = tdy1(i) End If Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 76 Next i For i = 1 To td1 - 1 For j = i + 1 To td1 If tdx1(i) > tdx1(j) Then tgx = tdx1(i) tdx1(i) = tdx1(j) tdx1(j) = tgx tgy = tdy1(i) tdy1(i) = tdy1(j) tdy1(j) = tgy End If Next j Next i td2 = td2 – 1 'Sap xep mang td2 va tim tung do nho nhat tdy2min = tdy2(1) For i = 1 To td2 - 1 If tdy2(i) < tdy2min Then tdy2min = tdy2(i) End If Next i For i = 1 To td2 - 1 For j = i + 1 To td2 If tdx2(i) > tdx2(j) Then tgx = tdx2(i) tdx2(i) = tdx2(j) tdx1(j) = tgx tgy = tdy2(i) tdy2(i) = tdy2(j) tdy2(j) = tgy End If Next j Next i Line (tdx2(td2) + 300, 0)-(tdx2(td2) + 300, 7000) 'phan ly ngoai td2 = td2 + 1 tdxmax = tdx2(td2 - 1) + 300 tdx2(td2) = tdx2(td2 - 1) + 300 tdy2(td2) = 7000 / 2 For s = 2 To t ' Tim toa do giua cac vat can tsxmax(s) = Ar(s) tsxmin(s) = Ar(dc(s)) For i = dc(s - 1) + 1 To dc(s) If Ar(i) > tsxmax(s) Then tsxmax(s) = Ar(i) tsymax(s) = Br(i) End If If Ar(i) < tsxmin(s) Then tsxmin(s) = Ar(i) tsymin(s) = Br(i) End If Next i Next s Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 77 End Sub ------------------------------------------------------------------------------------------------------------ Private Sub Command3_Click() ' xay dung do thi For i = 1 To td1 + td2' Khoi tao mang trong so For j = 1 To td1 + td2 ts(i, j) = maxint Next j Next i DrawWidth = 3 If ddx < tdx1(1) Then If ddy < tdy1max Then If Sqr((tdx1(1) - ddx) * (tdx1(1) - ddx) + (tdy1(1) - ddy) * (tdy1(1) - ddy)) < Sqr((tdx1(2) - ddx) * (tdx1(2) - ddx) + (tdy1(2) - ddy) * (tdy1(2) - ddy)) Then Line (ddx, ddy)-(tdx1(1), tdy1(1)), QBColor(5) qI = 1 Else Line (ddx, ddy)-(tdx1(2), tdy1(2)), QBColor(5) qI = 2 End If Else If Sqr((tdx2(1) - ddx) * (tdx2(1) - ddx) + (tdy2(1) - ddy) * (tdy2(1) - ddy)) < Sqr((tdx2(2) - ddx) * (tdx2(2) - ddx) + (tdy2(2) - ddy) * (tdy2(2) - ddy)) Then Line (ddx, ddy)-(tdx2(1), tdy2(1)), QBColor(5) qI = 1 Else Line (ddx, ddy)-(tdx2(2), tdy2(2)), QBColor(5) qI = 2 End If End If Else If ddx >= tdx2(td2) Then If ddy < tdy1max Then If Sqr((tdx1(td1) - ddx) * (tdx1(td1) - ddx) + (tdy1(td1) - ddy) * (tdy1(td1) - ddy)) < Sqr((tdx1(td1 - 1) - ddx) * (tdx1(td1 - 1) - ddx) + (tdy1(td1 - 1) - ddy) * (tdy1(td1 - 1) - ddy)) Then Line (ddx, ddy)-(tdx1(td1), tdy1(td1)), QBColor(5) qI = td1 Else Line (ddx, ddy)-(tdx1(td1 - 1), tdy1(td1 - 1)), QBColor(5) qI = td1 - 1 End If Else If Sqr((tdx2(td2) - ddx) * (tdx2(td2) - ddx) + (tdy2(td2) - ddy) * (tdy2(td2) - ddy)) < Sqr((tdx2(td2 - 1) - ddx) * (tdx2(td2 - 1) - ddx) + (tdy2(td2 - 1) - ddy) * (tdy2(td2 - 1) - ddy)) Then Line (ddx, ddy)-(tdx2(td2), tdy2(td2)), QBColor(5) qI = td2 Else Line (ddx, ddy)-(tdx2(td2 - 1), tdy2(td2 - 1)), QBColor(5) qI = td2 - 1 End If End If Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 78 Else i = 1 If ddy < tdy1max Then Do While tdx1(i) < ddx i = i + 1 Loop If dcx > tdx1(i) Then Line (ddx, ddy)-(tdx1(i), tdy1(i)), QBColor(5) qI = i Else Line (ddx, ddy)-(tdx1(i - 1), tdy1(i - 1)), QBColor(5) qI = i - 1 End If Else Do While tdx2(i) < ddx i = i + 1 Loop If dcx > tdx2(i) Then Line (ddx, ddy)-(tdx2(i), tdy2(i)), QBColor(5) qI = i Else Line (ddx, ddy)-(tdx2(i - 1), tdy2(i - 1)), QBColor(5) qI = i - 1 End If End If End If End If '******************************************** k1 = 1 For i = 1 To td1 – 1 'noi cac diem mau Line (tdx1(i), tdy1(i))-(tdx1(i + 1), tdy1(i + 1)), QBColor(5) ts(k1, k1 + 1) = Sqr((tdx1(i + 1) - tdx1(i)) * (tdx1(i + 1) - tdx1(i)) + (tdy1(i + 1) - tdy1(i)) * (tdy1(i + 1) - tdy1(i))) ts(k1 + 1, k1) = Sqr((tdx1(i + 1) - tdx1(i)) * (tdx1(i + 1) - tdx1(i)) + (tdy1(i + 1) - tdy1(i)) * (tdy1(i + 1) - tdy1(i))) k1 = k1 + 1 Next i Line (tdx1(td1), tdy1(td1))-(tdx2(td2), tdy2(td2)), QBColor(5) ts(k1, k1 + 1) = Sqr((tdx2(td2) - tdx1(td1)) * (tdx2(td2) - tdx1(td1)) + (tdy2(td2) - tdy1(td1)) * (tdy2(td2) - tdy1(td1))) ts(k1 + 1, k1) = Sqr((tdx2(td2) - tdx1(td1)) * (tdx2(td2) - tdx1(td1)) + (tdy2(td2) - tdy1(td1)) * (tdy2(td2) - tdy1(td1))) k1 = k1 + 1 Line (tdx1(1), tdy1(1))-(tdx2(1), tdy2(1)), QBColor(5) For i = 1 To td2 - 1 Line (tdx2(i), tdy2(i))-(tdx2(i + 1), tdy2(i + 1)), QBColor(5) ts(k1, k1 + 1) = Sqr((tdx2(i + 1) - tdx2(i)) * (tdx2(i + 1) - tdx2(i)) + (tdy2(i + 1) - tdy2(i)) * (tdy2(i + 1) - tdy2(i))) ts(k1 + 1, k1) = Sqr((tdx2(i + 1) - tdx2(i)) * (tdx2(i + 1) - tdx2(i)) + (tdy2(i + 1) - tdy2(i)) * (tdy2(i + 1) - tdy2(i))) k1 = k1 + 1 Next i k = 1'Ghi diem ngat Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 79 i = 1 For s = 2 To t - 1 Do While tdx1(i) tsxmax(s) And (i < k1) i = i + 1 Loop dn1(k) = i i = 1 Do While (tdx2(i) tsxmax(s)) And (i < k1) i = i + 1 Loop dn2(k) = i k = k + 1 Next s '***************************************************** 'Noi diem dich voi do thi If dcx > tdx2(td2) Then 'diem dich nam sau If dcy < tdy1max Then 'diem cuoi nam tren If Sqr((tdx1(td1) - dcx) * (tdx1(td1) - dcx) + (tdy1(td1) - dcy) * (tdy1(td1) - dcy)) < Sqr((tdx1(td1 - 1) - dcx) * (tdx1(td1 - 1) - dcx) + (tdy1(td1 - 1) - dcy) * (tdy1(td1 - 1) - dcy)) Then Line (dcx, dcy)-(tdx1(td1), tdy1(td1)), QBColor(5) qG = td1 Else Line (dcx, dcy)-(tdx1(td1 - 1), tdy1(td1 - 1)), QBColor(5) qG = td1 - 1 End If Else If Sqr((tdx2(td2) - dcx) * (tdx2(td2) - dcx) + (tdy2(td2) - dcy) * (tdy2(td2) - dcy)) < Sqr((tdx2(td2 - 1) - dcx) * (tdx2(td2 - 1) - dcx) + (tdy2(td2 - 1) - dcy) * (tdy2(td2 - 1) - dcy)) Then Line (dcx, dcy)-(tdx2(td2), tdy2(td2)), QBColor(5) qG = td2 Else Line (dcx, dcy)-(tdx2(td2 - 1), tdy2(td2 - 1)), QBColor(5) qG = td2 - 1 End If End If Else If dcx <= tdx1(1) Then ''diem dich nam truoc If dcy < tdy1max Then If Sqr((tdx1(1) - dcx) * (tdx1(1) - dcx) + (tdy1(1) - dcy) * (tdy1(1) - dcy)) < Sqr((tdx1(2) - dcx) * (tdx1(2) - dcx) + (tdy1(2) - dcy) * (tdy1(2) - dcy)) Then Line (dcx, dcy)-(tdx1(1), tdy1(1)), QBColor(5) qG = 1 Else Line (dcx, dcy)-(tdx1(2), tdy1(2)), QBColor(5) qG = 2 End If Else If Sqr((tdx2(1) - dcx) * (tdx2(1) - dcx) + (tdy2(1) - dcy) * (tdy2(1) - dcy)) < Sqr((tdx2(2) - dcx) * (tdx2(2) - dcx) + (tdy2(2) - dcy) * (tdy2(2) - dcy)) Then Line (dcx, dcy)-(tdx2(1), tdy2(1)), QBColor(5) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 80 qG = 1 Else Line (dcx, dcy)-(tdx2(2), tdy2(2)), QBColor(5) qG = 2 End If End If Else 'diem dich nam trong vung phan ly j = 1 If dcy < tdy1max Then Do While (tdx1(j) < dcx) And (j < td1) j = j + 1 Loop If ddx > tdx1(j) Then Line (dcx, dcy)-(tdx1(j), tdy1(j)), QBColor(5) qG = j Else Line (dcx, dcy)-(tdx1(j - 1), tdy1(j - 1)), QBColor(5) qG = j - 1 End If Else Do While (tdx2(j) < dcx) And (j <= td2) j = j + 1 Loop If ddx < tdx2(j) Then Line (dcx, dcy)-(tdx2(j - 1), tdy2(j - 1)), QBColor(5) qG = j - 1 Else Line (dcx, dcy)-(tdx2(j), tdy2(j)), QBColor(5) qG = j End If End If End If End If '************************************************* 'Duong di giua cac vat can For s = 2 To t - 1 Line (tsxmax(s), tsymax(s) / 2)-(tsxmax(s) + (tsxmin(s + 1) - tsxmax(s)) / 2, tsymax(s) + (tsymin(s + 1) + (7000 - tsymin(s + 1)) / 2 - tsxmax(s)) / 2), QBColor(5) tg1 = tsxmax(s) + (tsxmin(s + 1) - tsxmax(s)) / 2 - tsxmax(s) tg2 = tsymax(s) + (tsymin(s + 1) + (7000 - tsymin(s + 1)) / 2 - tsxmax(s)) / 2 - tsymax(s) / 2 k1 = k1 + 1 Line (tsxmax(s) + (tsxmin(s + 1) - tsxmax(s)) / 2, tsymax(s) + (tsymin(s + 1) + (7000 - tsymin(s + 1)) / 2 - tsxmax(s)) / 2)-(tsxmax(s), tsymax(s) + (7000 - tsymax(s)) / 2), QBColor(5) tg1 = tsxmax(s) - tsxmax(s) + (tsxmin(s + 1) - tsxmax(s)) / 2 tg2 = tsymax(s) + (7000 - tsymax(s)) / 2 - tsymax(s) + (tsymin(s + 1) + (7000 - tsymin(s + 1)) / 2 - tsxmax(s)) / 2 k1 = k1 + 1 Next s End Sub Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 81 ------------------------------------------------------------------------------------------------- Private Sub Command4_Click() ' Tim duong di ngan nhat s = qI n = td1 + td2 - 1 t = qG ' Khoi tao For v = 1 To n d(v) = ts(s, v) truoc(v) = s final(v) = False Next v truoc(s) = 0 d(s) = 0 final(s) = True 'buoc lap Do While Not (final(t)) minp = maxint For v = 1 To n If (Not (final(v))) And (minp > d(v)) Then u = v minp = d(v) End If Next v final(u) = True If Not (final(t)) Then For v = 1 To n If (Not (final(v))) And (d(u) + ts(u, v) < d(v)) Then d(v) = d(u) + ts(u, v) truoc(v) = u End If Next v End If Loop DrawWidth = 5 i = t ' noi duong dan giai phap If (ddy < tdy1max) And (dcy < tdy1max) Then ' hai diem thuoc nua tren Line (ddx, ddy)-(tdx1(qI), tdy1(qI)), &HFF& Do While i s Line (tdx1(i), tdy1(i))-(tdx1(truoc(i)), tdy1(truoc(i))), &HFF& i = truoc(i) Loop Line (dcx, dcy)-(tdx1(qG), tdy1(qG)), &HFF& Else If (ddy > tdy1max) And (dcy > tdy1max) Then 'Hai diem thuoc nua duoi Line (ddx, ddy)-(tdx2(qI), tdy2(qI)), &HFF& Do While i s Line (tdx2(i), tdy2(i))-(tdx2(truoc(i)), tdy2(truoc(i))), &HFF& i = truoc(i) Loop Line (dcx, dcy)-(tdx2(qG), tdy2(qG)), &HFF& Else Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 82 If (ddy < tdy1max) Then ' qI nua tren qG nua duoi Line (ddx, ddy)-(tdx1(qI), tdy1(qI)), &HFF& If tdx1(dn1(1)) < tdx1(qI) Then k1 = dn1(1) k2 = qI - 1 Else k1 = qI k2 = dn1(1) - 1 End If For i = k1 To k2 Line (tdx1(i), tdy1(i))-(tdx1(i + 1), tdy1(i + 1)), &HFF& Next i s = 2 Line (tsxmax(s), tsymax(s) / 2)-(tsxmax(s) + (tsxmin(s + 1) - tsxmax(s)) / 2, tsymax(s) + (tsymin(s + 1) + (7000 - tsymin(s + 1)) / 2 - tsxmax(s)) / 2), &HFF& Line (tsxmax(s) + (tsxmin(s + 1) - tsxmax(s)) / 2, tsymax(s) + (tsymin(s + 1) + (7000 - tsymin(s + 1)) / 2 - tsxmax(s)) / 2)-(tsxmax(s), tsymax(s) + (7000 - tsymax(s)) / 2), &HFF& If tdx2(dn2(1)) < tdx2(qG) Then k1 = dn2(1) k2 = qG - 1 Else k1 = qG k2 = dn2(1) - 1 End If For i = k1 To k2 Line (tdx2(i), tdy2(i))-(tdx2(i + 1), tdy2(i + 1)), &HFF& Next i Line (dcx, dcy)-(tdx2(qG), tdy2(qG)), &HFF& Else ' qI nua duoi qG nua tren Line (ddx, ddy)-(tdx2(qI), tdy2(qI)), &HFF& If tdx2(qI) < tdx2(dn2(1)) Then k1 = qI k2 = dn2(1) - 1 Else k2 = qI - 1 k1 = dn2(1) End If For i = k1 To k2 Line (tdx2(i), tdy2(i))-(tdx2(i + 1), tdy2(i + 1)), &HFF& Next i s = 2 Line (tsxmax(s), tsymax(s) / 2)-(tsxmax(s) + (tsxmin(s + 1) - tsxmax(s)) / 2, tsymax(s) + (tsymin(s + 1) + (7000 - tsymin(s + 1)) / 2 - tsxmax(s)) / 2), &HFF& Line (tsxmax(s) + (tsxmin(s + 1) - tsxmax(s)) / 2, tsymax(s) + (tsymin(s + 1) + (7000 - tsymin(s + 1)) / 2 - tsxmax(s)) / 2)-(tsxmax(s), tsymax(s) + (7000 - tsymax(s)) / 2), &HFF& If tdx1(qG) < tdx1(dn1(1)) Then k1 = qG k2 = dn1(1) - 1 Else k1 = dn1(1) k2 = qG - 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 83 End If For i = k1 To k2 Line (tdx1(i), tdy1(i))-(tdx1(i + 1), tdy1(i + 1)), &HFF& Next i Line (dcx, dcy)-(tdx1(qG), tdy1(qG)), &HFF& End If End If End If End Sub ----------------------------------------------------------------------------------------- Private Sub Form_Load() n = 1 t = 1 dc(1) = 0 dk1 = False td1 = 1 td2 = 1 ddx = 0 ddy = 0 dcx = 0 dcy = 0 maxint = 100000 End Sub -------------------------------------------------------------------------------------------------------------------- Private Sub Form_MouseDown(Button As Integer, Shift As Integer, x As Single, y As Single) If O2.Value = True Then Select Case Button Case vbLeftButton If c 2 Then Circle (x, y), 30, QBColor(2) a = x b = y c = 2 dx = a dy = b Ar(n) = a Br(n) = b Else n = n + 1 Circle (x, y), 30, QBColor(2) DrawWidth = 7 Line (a, b)-(x, y), QBColor(2) a = x b = y Ar(n) = a Br(n) = b End If Case vbRightButton c = 1 DrawWidth = 7 Line (dx, dy)-(a, b), QBColor(2) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 84 n = n + 1 Ar(n) = dx Br(n) = dy t = t + 1 dc(t) = n n = n + 1 End Select Else If O1.Value = True Then Select Case Button Case vbLeftButton Circle (ddx, ddy), 30, &H8000000F Circle (x, y), 30, QBColor(3) ddx = x ddy = y Print "qI" Case vbRightButton Circle (dcx, dcy), 30, &H8000000F Circle (x, y), 30, QBColor(4) dcx = x dcy = y Print "qG" End Select Else MsgBox "Hay chon mot nut...!" End If End If End Sub