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

§¹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 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è 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 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 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 gi¶i 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 c¶n........................................................14 H×nh 1.6:Robot tù x©y dùng b¶n ®å 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 c¶i 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µ R 2 .............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 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 gi¶i 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 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 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 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¬ 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 “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¬ 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. 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µ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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. Chương 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 Ngƣời viÕt luËn v¨n NguyÔn ThÞ Thu Thuû Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 7 Ch•¬ng I Giíi thiÖu bµi to¸n lËp lé tr×nh cho Robot 1.1. ROBOT NHÂN T¹O. Cùng với sự phát triển của khoa học, công nghệ robot ngày càng được ứng dụng rộng rãi trong các lĩnh vực của đời sống xã hội. Chúng có thể là những thiết bị điều khiển tự động trong các dây truyền công nghiệp, hoặc có thể là những robot làm việc trong những môi trường phức tạp mà con người đôi khi không thể tiếp cận được như: môi trường nhiệt độ cao, áp suất lớn hay ở ngoài khoảng không vũ trụ. Không chỉ có vậy robot còn được ứng dụng rất nhiều trong đời sống ví dụ như: Robot lau dọn sàn nhà, robot hướng dẫn di chuyển, robot phục vụ trong các toà nhà cao tầng, robot phẫu thuật,... Robot được ứng dụng rộng rãi và có nhiều tính năng ưu việt như vậy song không phải ai cũng có thể hiểu về nguyên lý của những tác vụ mà robot có thể thực hiện. Sau đây sẽ là những trình bày sơ lược về nguyên tắc cấu tạo và nguyên lý làm việc của một mobile robot. 1.1.1. Tổng quan Về cấu tạo: Robot phải dược trang bị bộ cảm nhận để cảm nhận các thông tin về môi trường như: sensor, encoder. Các bộ phận thực hiện hành động: bánh xe để chuyển động, cánh tay robot… Các tri thức mà robot cần được trang bị là: Cấu trúc của môi trường làm việc, các hoàn cảnh mà robot có thể gặp và các hành động mà robot cần thực hiện trong các hoàn cảnh đó, ... Các tri thức này cần phải được thể hiện mộ t cách thích hợp sao cho thuận tiện cho việc lưu trữ, tìm kiếm và suy diễn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 8 Các khả năng của robot: Robot cần có khả năng phân biệt được các đối tượng mà nó gặp, thực hiện các thao tác, di chuyển an toàn trong môi trường sao cho đường đi là tối ưu và không va trạm với các vật cản. 1.1.2. Giải pháp thiết kế Để thiết kế robot ta phải hoàn thiện các công việc sau: Xem robot như một đối tượng lập trình bao gồm: - Dữ liệu: Các trạng thái của môi trường làm việc, giá trị của sensor, encoder... - Tác vụ: Là tập các hành động cơ bản mà robot có thể thực hiện như: tiến, lùi, rẽ trái, rẽ phải, ... Mô hình hoá môi trường làm việc. Mô hình hoá đối tượng robot sẽ gặp, xử lý các tác vụ trong môi trường làm việc, cùng với việc xử lý dữ liệu và các trạng thái trong môi trường. Nhúng các giải thuật tìm đường và giải thuật xử lý sự kiện cho robot để có một đường đi tốt từ vị trí ban đầu tới đích và xử lý các tình huống ngoại lệ như va chạm. Phân chia và module hoá các khối trên robot. Xây dựng các thành phần robot bao gồm: Lập trình, mạch phần cứng, cơ cấu cơ khí. Cả ba quá trình này phải triển khai đồng bộ với nhau và chúng có tác động rất lớn tới nhau, sự hoàn thiện phần này là tiền đề để xây dựng phần kia. Cơ chế hiển thị và Debug lỗi qua các giao tiếp Led/LCD hay với PC. Các thành phần cấu thành nên robot có thể được mô hình hoá bởi sơ đồ sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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. BÀI TOÁN 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 bởi Trung tâm Học liệu – Đại học Thái Nguyên 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 bởi Trung tâm Học liệu – Đại học Thái Nguyên 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