Xây dựng một Agent tự nhận thức để tìm kiếm

c. Töø ñoù coù theå phaân chia caùc lónh vöïc nghieân cöùu vaø öùng duïng quan troïng cuûa trí tueä nhaân taïo theo 4 höôùng cô baûn sau : Moâ hình hoaù treân maùy tính nhöõng chöùc naêng khaùc nhau trong quaù trình saùng taïo nhö : caùc troø chôi, chöùng minh töï ñoäng caùc ñònh lyù, toång hôïp töï ñoäng caùc chöông trình … Naâng cao khaû naêng trí tueä “beân ngoaøi” cuûa maùy tính gaén lieàn vôùi caùc giao tieáp, hoäi thoaïi baèng caùch söû duïng caùc kyõ thuaät suy dieãn vaø tìm kieám. Naâng cao khaû naêng trí tueä “beân trong” cuûa maùy tính treân cô sôû cheá taïo caùc maùy tính theá heä môùi vôùi kieán truùc vaät lyù môùi döïa treân caùc nguyeân lyù cuûa trí tueä nhaân taïo. Cheá taïo caùc Robot thoâng minh coù khaû naêng thöïc hieän nhöõng thao taùc phöùc taïp, coù theå ”suy nghó” vaø “haønh ñoäng” ñeå ñaït ñeán muïc ñích ñaõ ñaët ra. 3. Caùc phöông phaùp vaø kyõ thuaät Trí Tueä Nhaân Taïo Caùc baøi toaùn trí tueä nhaân taïo traûi roäng trong nhieàu lónh vöïc khaùc nhau neân vieäc giaûi quyeát chuùng ñoøi hoûi phaûi ñaùp öùng nhöõng yeâu caàu veà phöông dieän kyõ thuaät tin hoïc vaø caû veà thieát bò töông öùng. Caùc phöông phaùp vaø kyõ thuaät trí tueä nhaân taïo cô baûn bao goàm: Caùc phöông phaùp bieåu dieãn tri thöùc vaø coâng ngheä xöû lyù tri thöùc. Caùc phöông phaùp giaûi quyeát vaán ñeà. Caùc phöông phaùp Heuristic. Caùc phöông phaùp hoïc. Caùc ngoân ngöõ trí tueä nhaân taïo. Xöû lyù danh saùch, kyõ thuaät ñeä quy, kyõ thuaät quay lui … laø nhöõng kyõ thuaät cô baûn cuûa tin hoïc truyeàn thoáng coù lieân quan tröïc tieáp ñeán trí tueä nhaân taïo. Vì ñeà taøi söû duïng caùc phöông phaùp tìm kieám Heuristic vaø phöông phaùp hoïc neân ôû ñaây chæ ñeà caäp ñeán hai phöông phaùp naøy. Coøn nhöõng phöông phaùp khaùc neáu coù nhu caàu tìm hieåu theâm, xin xem theâm ôû taøi lieäu tham khaûo. 4. Caùc Giaûi Thuaät Tìm Kieám Heuristic Laäp trình Heuristic laø moät höôùng tieáp caän quan troïng trong vieäc xaây döïng caùc heä thoáng trí tueä nhaân taïo. Lyù thuyeát tìm kieám Heuristic bao goàm caùc phöông phaùp vaø caùc kyõ thuaät tìm kieám, söû duïng caùc tri thöùc ñaëc bieät naûy sinh töø baûn thaân baøi toaùn caàn giaûi ñeå ruùt ngaén quaù trình giaûi, nhanh choùng ñi ñeán keát quaû mong muoán. Kyõ thuaät cô baûn döïa treân caùc tri thöùc Heuristic hay ñöôïc söû duïng trong thöïc tieãn laø caùc haøm ñaùnh giaù. 4.1 Giaûi thuaät leo ñoài Giaûi thuaät leo ñoài laø moät giaûi thuaät tìm kieám döïa treân haøm ñaùnh giaù theo chieàu saâu nghóa laø chæ taäp trung tìm kieám theo moät höôùng. Nhöõng neùt chính cuûa thuaät giaûi Thuaät giaûi söû duïng 2 danh saùch: Danh saùch môû Open, chöùa caùc ñænh seõ ñöôïc xem xeùt ôû caùc böôùc keá tieáp. Danh saùch ñoùng Close, chöùa caùc ñænh ñaõ ñöôïc xem xeùt. Caùc ñoái töôïng chính trong thuaät giaûi: Ñænh baét ñaàu s Ñænh keát thuùc g Ñænh ñang xeùt n Danh saùch B(n) chöùa caùc ñænh ñi ñöôïc töø ñænh n. Thuaät giaûi: Open.Store(s) while not Open.Empty() do n = Open.Retrieve() Close.Store(n) if n == g then return true for m Î B(n) do Open.Store(m) return false Danh saùch môû Open ñöôïc söû duïng trong tröôøng hôïp naøy laø Stack. 4.2 Giaûi thuaät A*: Giaûi thuaät A* laø moät giaûi thuaät tìm kieám döïa treân haøm ñaùnh giaù theo chieàu roäng vôùi caùc thoâng tin Heuristic cho pheùp saép xeáp laïi caùc ñænh. Nhöõng neùt chính cuûa thuaät giaûi: Thuaät giaûi cuõng söû duïng 2 danh saùch: Danh saùch môû Open, chöùa caùc ñænh seõ ñöôïc xem xeùt ôû caùc böôùc keá tieáp. Danh saùch ñoùng Close, chöùa caùc ñænh ñaõ ñöôïc xem xeùt. Caùc ñoái töôïng chính trong thuaät giaûi: Ñænh baét ñaàu s Ñænh keát thuùc g Ñænh ñang xeùt n Danh saùch B(n) chöùa caùc ñænh ñi ñöôïc töø ñænh n. Thuaät giaûi A*: 1. Open.Store(s) 2. while not Open.Empty() do 2.1 n = Open.Retrieve() 2.2 Close.Store(n) 2.3 if (n == g) then return true 2.4 for m Î B(n) do 2.4.1 2.4.2 if (m Ï Open È Close) then Open. Store(m) 2.4.3 if (m == (m’ ÎOpenÈClose) && ^f(m) < ^f(m’) then 2.4.3 .1 <ñaët laïi tham chieáu cho m’) 2.4.3 .2 if (m’ Î Close ) < chuyeån m’ qua Open ) 3. return false Danh saùch môû Open ñöôïc söû duïng trong tröôøng hôïp naøy laø Queue. III. LAÄP TRÌNH HÖÔÙNG ÑOÁI TÖÔÏNG VÔÙI VISUAL C++ Thöïc teá, moïi thöù trong theá giôùi thöïc ñeàu coù theå ñöôïc xem nhö ñoái töôïng. Do ñoù, ñeå moâ phoûng theá giôùi thöïc thì khoâng coù höôùng tieáp caän naøo toát hôn höôùng ñoái töôïng. Trong soá caùc ngoân ngöõ hoã trôï höôùng ñoái töôïng thì C++ ñöôïc xem laø ngoân ngöõ laäp trình thoâng duïng nhaát. Hieän nay, treân thò tröôøng coù nhieàu coâng cuï hoã trôï laäp trình treân C++ nhö Borland C++, Watson C++, Visual C++… trong ñoù Visual C++ cuûa haõng Microsoft ñöôïc öa chuoäng nhaát vì tính thaân thieän, deã söû duïng vaø hoã trôï trieån khai öùng duïng nhanh. Vì theá, toâi choïn Visual C++ laøm coâng cuï phaùt trieån öùng duïng cuûa mình trong ñeà taøi naøy. 1. Khaùi nieäm veà laäp trình höôùng ñoái töôïng: 1.1 Toång quan: Laäp trình höôùng ñoái töôïng (Object-Oriented Programming – goïi taét laø OOP), hay chi tieát hôn laø laäp trình ñònh höôùng ñoái töôïng, laø moät phöông phaùp laäp trình laáy ñoái töôïng (object) laøm neàn taûng ñeå xaây döïng thuaät giaûi, xaây döïng chöông trình. Laäp trình höôùng ñoái töôïng ñaët troïng taâm vaøo ñoái töôïng - yeáu toá quan troïng trong quaù trình phaùt trieån chöông trình- vaø khoâng cho pheùp döõ lieäu bieán ñoäng töï do trong heä thoáng. Döõ lieäu ñöôïc gaén chaët vôùi caùc haøm thaønh caùc vuøng rieâng maø chæ coù caùc haøm ñoù taùc ñoäng leân vaø caám caùc haøm beân ngoaøi truy caäp tôùi moät caùch tuyø tieän. Laäp trình höôùng ñoái töôïng cho pheùp chuùng ta phaân tích baøi toaùn thaønh caùc thöïc theå ñöôïc goïi laø caùc ñoái töôïng vaø sau ñoù xaây döïng caùc döõ lieäu cuøng caùc haøm xung quanh caùc ñoái töôïng ñoù. Caùc ñoái töôïng coù theå taùc ñoäng, trao ñoåi thoâng tin vôùi nhau thoâng qua cô cheá truyeàn nhaän thoâng ñieäp (message). Vieäc toå chöùc moät chöông trình höôùng ñoái töôïng coù theå ñöôïc moâ taû nhö sau: Ñoái töôïng A Döõ lieäu Ñoái töôïng B Döõ lieäu Ñoái töôïng C Döõ lieäu message Laäp trình höôùng ñoái töôïng coù caùc ñaëc tính chuû yeáu sau: Taäp trung vaøo döõ lieäu thay cho caùc haøm. Chöông trình ñöôïc chia thaønh caùc ñoái töôïng. Caáu truùc döõ lieäu ñöôïc thieát keá sao cho ñaëc taû ñöôïc ñoái töôïng. Caùc haøm thao taùc treân caùc vuøng döõ lieäu cuûa ñoái töôïng ñöôïc gaén vôùi caáu truùc döõ lieäu ñoù. Döõ lieäu ñöôïc ñoùng goùi laïi, ñöôïc che giaáu vaø khoâng cho pheùp caùc haøm ngoaïi lai truy caäp töï do. Caùc ñoái töôïng taùc ñoäng vaø trao ñoåi thoâng tin vôùi nhau qua caùc haøm Coù theå deã daøng boå sung döõ lieäu vaø caùc haøm môùi vaøo ñoái töôïng naøo ñoù khi caàn thieát. Chöông trình ñöôïc thieát keá theo caùch tieáp caän töø döôùi leân (bottom-up). Sau ñaây laø moät soá khaùi nieäm ñöôïc söû duïng trong laäp trình höôùng ñoái töôïng. 1.2 Moät soá khaùi nieäm: Ñoái töôïng (object) Ñoái töôïng laø söï keát hôïp giöõa döõ lieäu vaø phöông thöùc thao taùc treân döõ lieäu ñoù. Coù theå ñöa ra coâng thöùc phaûn aùnh baûn chaát kyõ thuaät cuûa laäp trình höôùng ñoái töôïng nhö sau: Ñoái töôïng = döõ lieäu + phöông thöùc Lôùp (class) Lôùp laø moät khaùi nieäm môùi trong laäp trình höôùng ñoái töôïng so vôùi caùc kyõ thuaät laäp trình khaùc. Ñoù laø moät taäp caùc ñoái töôïng coù caáu truùc döõ lieäu vaø caùc phöông thöùc gioáng nhau (hay noùi caùch khaùc laø moät taäp caùc ñoái töôïng cuøng loaïi). Nhö vaäy khi coù moät lôùp thì chuùng ta seõ bieát ñöôïc moät moâ taû caáu truùc döõ lieäu vaø phöông thöùc cuûa caùc ñoái töôïng thuoäc lôùp ñoù. Moãi ñoái töôïng seõ laø moät theå hieän cuï theå (instance) cuûa lôùp ñoù. Trong laäp trình, chuùng ta coù theå coi moät lôùp nhö laø moät kieåu coøn caùc ñoái töôïng seõ laø caùc bieán coù kieåu cuûa lôùp. Nguyeân taéc ñoùng goùi döõ lieäu Trong laäp trình höôùng ñoái töôïng ta ñaõ thaáy caùc haøm hay thuû tuïc ñöôïc söû duïng maø khoâng caàn bieát noäi dung cuï theå cuûa noù. Ngöôøi söû duïng chæ caàn bieát chöùc naêng cuûa haøm cuõng nhö caùc tham soá caàn truyeàn vaøo ñeå goïi haøm thöïc thi maø khoâng caàn quan taâm ñeán nhöõng leänh cuï theå beân trong noù. Ngöôøi ta goïi ñoù laø söï ñoùng goùi veà chöùc naêng. Trong laäp trình höôùng ñoái töôïng, khoâng nhöõng chöùc naêng ñöôïc ñoùng goùi maø caû döõ lieäu cuõng nhö vaäy. Vôùi moãi ñoái töôïng, ngöôøi ta khoâng theå truy caäp tröïc tieáp vaøo caùc thaønh phaàn döõ lieäu cuûa noù maø phaûi thoâng qua caùc thaønh phaàn chöùc naêng (caùc phöông thöùc) ñeå laøm vieäc ñoù. Chuùng ta seõ thaáy söï ñoùng goùi thöïc söï veà döõ lieäu chæ coù trong moät ngoân ngöõ laäp trình höôùng ñoái töôïng “thuaàn khieát” (pure) theo nghóa caùc ngoân ngöõ ñöôïc thieát keá ngay töø ñaàu chæ cho laäp trình höôùng ñoái töôïng. Coøn ñoái vôùi caùc ngoân ngöõ “lai” (hybrid) ñöôïc xaây döïng treân caùc ngoân ngöõ khaùc (ban ñaàu chöa phaûi laø höôùng ñoái töôïng) nhö C++ vaãn coù nhöõng ngoaïi leä nhaát ñònh vi phaïm nguyeân taéc ñoùng goùi döõ lieäu. Tính thöøa keá (inheritance) Moät khaùi nieäm quan troïng cuûa laäp trình höôùng ñoái töôïng laø söï thöøa keá. Söï thöøa keá cho pheùp chuùng ta ñònh nghóa moät lôùp môùi treân cô sôû caùc lôùp ñaõ toàn taïi coù boå sung nhöõng phöông thöùc hay caùc thaønh phaàn döõ lieäu môùi. Khaû naêng keá thöøa cho pheùp chuùng ta söû duïng laïi moät caùch deã daøng caùc module chöông trình maø khoâng caàn thay ñoåi caùc module ñoù. Ñaây laø moät ñieåm maïnh cuûa laäp trình höôùng ñoái töôïng so vôùi laäp trình caáu truùc. Tính ña hình (polymorphime) Tính ña hình xuaát hieän khi coù khaùi nieäm keá thöøa. Giaû söû chuùng ta coù moät keá thöøa lôùp hình töù giaùc vaø tam giaùc töø lôùp hình ña giaùc (hình tam giaùc vaø töù giaùc coù ñaày ñuû caùc thuoäc tính vaø tính chaát cuûa moät hình ña giaùc). Luùc naøy moät ñoái töôïng thuoäc lôùp hình tam giaùc hay töù giaùc ñeàu coù theå hieåu raèng noù laø moät hình ña giaùc. Maët khaùc vôùi moãi ña giaùc ta coù theå tính dieän tích cuûa noù. Nhö vaäy laøm theá naøo maø moät ña giaùc coù theå söû duïng ñuùng coâng thöùc ñeå tính dieän tích phuø hôïp vôùi noù laø hình tam giaùc hay töù giaùc. Ta goïi ñoù laø tính ña hình. 1.3 Caùc öu ñieåm cuûa laäp trình höôùng ñoái töôïng: Laäp trình höôùng ñoái töôïng ñem laïi moät soá lôïi theá cho ngöôøi thieát keá laãn ngöôøi laäp trình. Caùch tieáp caän höôùng ñoái töôïng giaûi quyeát ñöôïc nhieàu vaán ñeà toàn taïi trong quaù trình phaùt trieån phaàn meàm vaø taïo ra ñöôïc nhöõng phaàn meàm coù ñoä phöùc taïp vaø chaát löôïng cao. Phöông phaùp naøy môû ra moät trieån voïng to lôùn cho ngöôøi laäp trình. Nhöõng öu ñieåm chính cuûa laäp trình höôùng ñoái töôïng laø: Thoâng qua nguyeân lyù keá thöøa, chuùng ta coù theå loaïi boû ñöôïc nhöõng chöông trình laëp laïi trong quaù trình moâ taû caùc lôùp vaø coù theå môû roäng khaû naêng söû duïng cuûa caùc lôùp ñaõ xaây döïng maø khoâng caàn phaûi vieát laïi. Chöông trình ñöôïc xaây döïng töø nhöõng ñôn theå (ñoái töôïng) trao ñoåi vôùi nhau neân vieäc thieát keá vaø laäp trình seõ ñöôïc thöïc hieän theo quy trình nhaát ñònh chöù khoâng phaûi döïa vaøo kinh nghieäm vaø kyõ thuaät nhö tröôùc nöõa. Ñieàu naøy ñaûm baûo ruùt ngaén ñöôïc thôøi gian xaây döïng heä thoáng vaø taêng naêng suaát lao ñoäng. Nguyeân lyù ñoùng goùi hay che giaáu thoâng tin giuùp laäp trình vieân taïo ra ñöôïc nhöõng chöông trình an toaøn khoâng bò thay ñoåi bôûi nhöõng ñoaïn chöông trình khaùc. Coù theå xaây döïng ñöôïc aùnh xaï caùc ñoái töôïng cuûa baøi toaùn vaøo ñoái töôïng chöông trình. Caùch tieáp caän thieát keá ñaët troïng taâm vaøo döõ lieäu, giuùp chuùng ta xaây döïng ñöôïc moâ hình chi tieát vaø deã daøng caøi ñaët hôn. Caùc heä thoáng höôùng ñoái töôïng deã môû roäng, naâng caáp thaønh nhöõng heä lôùn hôn. Kyõ thuaät truyeàn thoâng ñieäp trong vieäc trao ñoåi thoâng tin giöõa caùc ñoái töôïng laøm cho vieäc moâ taû giao dieän vôùi caùc heä thoáng beân ngoaøi trôû neân ñôn giaûn hôn. Coù theå quaûn lyù ñöôïc ñoä phöùc taïp cuûa nhöõng saûn phaåm phaàn meàm. Vôùi nhieàu ñaëc tính phong phuù cuûa laäp trình höôùng ñoái töôïng noùi rieâng, cuûa phöông phaùp phaân tích thieát keá vaø phaùt trieån höôùng ñoái töôïng noùi chung, chuùng ta hy voïng coâng nghieäp phaàn meàm seõ coù nhöõng caûi tieán vöôït baäc khoâng nhöõng veà chaát löôïng maø coøn gia taêng nhanh veà soá löôïng trong töông lai. 2. Ngoân ngöõ laäp trình Visual C++ treân moâi tröôøng Windows 2.1 Toång quan: Nhö chuùng ta ñaõ bieát, caùc chöông trình öùng duïng ngaøy nay thöôøng laø phöùc taïp vaø quy moâ hôn so vôùi tröôùc ñaây. Hôn nöõa, beân caïnh quy moâ lôùn vaø phöùc taïp thì giao dieän ñoà hoïa gaàn nhö khoâng theå thieáu trong nhöõng chöông trình öùng duïng naøy. Tuy nhieân, cho duø caùc chöông trình öùng duïng ngaøy caøng ñoøi hoûi tính quy moâ, phöùc taïp hôn thì ngöôøi laäp trình vaãn coù khaû naêng giaûm thieåu caùc coâng vieäc cuûa mình neáu hoï choïn ñöôïc moät coâng cuï laäp trình hôïp lyù. Visual C++ laø moät trong nhöõng coâng cuï noùi treân. Vôùi code-generating wizards, Visual C++ coù theå taïo ra khung söôøn cho caùc chöông trình öùng duïng thöïc thi trong moâi tröôøng Windows trong voøng vaøi giaây. Caùc lôùp thö vieän ñi keøm vôùi Visual C++ nhö laø Microsoft Foundation Classes (MFC) ñaõ trôû thaønh moät trong caùc tieâu chuaån ñeå phaùt trieån caùc phaàn meàm döôùi moâi tröôøng Windows cho caùc trình bieân dòch C khaùc nhau. Beân caïnh ñoù, caùc coâng cuï soaïn thaûo khaû kieán cuõng taïo ra cho chuùng ta caùc coâng cuï höõu hieäu ñeå coù theå taïo caùc menu vaø caùc hoäp hoäi thoaïi. Noùi toùm laïi, vieäc nghieân cöùu Visual C++ laø moät vieäc laøm caàn thieát cho caùc nhaø laäp trình öùng duïng khi vieát caùc chöông trình thöïc thi trong moâi tröôøng Windows vaø giao dieän ñoà hoïa. Ñeå cung caáp cho laäp trình vieân moät moâi tröôøng laøm vieäc hieäu quaû, Microsoft Developer Studio ñaõ keát hôïp caùc giai ñoaïn cuûa vieäc laäp trình nhö soaïn thaûo, bieân dòch vaø kieåm tra loãi laïi thaønh moät giao dieän duy nhaát, ñieàu ñoù coù nghóa chuùng ta coù theå caøi ñaët hay xoaù boû caùc Breakpoint phuïc vuï cho vieäc Debug chöông trình trong cuøng moät giao dieän vôùi vieäc soaïn thaûo phaàn Source code. Hôn theá nöõa, khi chuùng ta tieán haønh xaây döïng moät ñeà aùn, moâi tröôøng phaùt trieån tích hôïp (IDE - Integrated Development Environment) coù theå phaùt hieän caùc loãi vaø cho pheùp chuùng ta tieáp caän ngay ñeán vò trí loãi ñoù moät caùch nhanh choùng cho duø taäp tin chöùa caùc loãi naøy chöa ñöôïc môû. Vôùi Microsoft Visual C++, chöông trình öùng duïng thöôøng ñöôïc xaây döïng treân cô sôû caùc lôùp (classes). Coù raát nhieàu lôùp khaùc nhau ñaõ ñöôïc xaây döïng saün thaønh thö vieän ñeå phuïc vuï cho ngöôøi laäp trình. Chaúng haïn nhö lôùp CDC laø lôùp phuïc vuï raát ñaéc löïc cho vieäc veõ hình trong caùc öùng duïng vieát baèng Visual C++. Lôùp CDC Moät caùch chuyeân duïng, lôùp CDC ñöôïc thieát keá cho muïc ñích chính laø veõ hình ñeå taïo nhöõng hình aûnh thoâng baùo hay ñeå thöïc thi haøm OnDraw() khi chuùng ta caàn laøm vieäc trong caùc cöûa soå. Trong thöïc teá thì lôùp CDC ñöôïc thieát keá bao goàm hai nhoùm Device Context: moät duøng cho vieäc quaûn lyù caùc quaù trình veõ vaø moät duøng cho vieäc quaûn lyù caùc quaù trình hoûi ñaùp – truy vaán (query). Vieäc quaûn lyù quaù trình veõ treân caùc DC ñöôïc thöïc thi bôûi m_hDC vaø vieäc quaûn lyù caùc quaù trình chaát vaán laø do m_hAttribDC. Khi chuùng ta can thieäp vaøo CDC duø vôùi moät coâng vieäc sô ñaúng nhaát thì ñaùp öùng töông töï seõ xaûy ra cho DC töông öùng. Do ñoù chuùng ta coù theå thöïc hieän caùc coâng vieäc moät caùch ñôn giaûn laø söû duïng caùc haøm thaønh phaàn cuûa CDC. Ñoàng thôøi Windows cuõng giôùi thieäu moät thö vieän GDI (Graphic Device Interface). Thö vieän naøy giuùp cho chöông trình vieát ra coù theå tieáp caän driver Video vaø Printer cuûa heä thoáng moät caùch deã daøng. Chöông trình naøy coù theå goïi caùc haøm chöùc naêng cuûa GDI, tham khaûo caáu truùc cuûa caùc döõ lieäu baèng caùch goïi Device Context. Windows seõ aùnh xaï caáu truùc Device Context thaønh Physical Device vaø ñöa ra Input/Output töông öùng. Microsoft Developer Studio vaø tieán trình xaây döïng: Visual C++ laø moät thaønh phaàn cuûa Microsoft Developer Studio laø IDE (Integrated Development Environtment). IDE coù nguoàn goác töø Visual Workbench döïa treân Quick C cho Window. Microsoft Developer Studio cung caáp khaû naêng : Help Online laøm vieäc nhö moät Web Browser. AppWizard Coù theå xem Project ôû nhieàu khía caïnh (editor, workspace) ClassWizard Xaây döïng giao dieän goàm trình ñôn vaø caùc khung ñoái thoaïi Compiling, Linking Debugging Tieán trình xaây döïng moät öùng duïng cuûa Visual C++ : ÔÛ ñaây, trong phaïm vi ñeà taøi naøy, chuùng ta chæ nghieân cöùu laäp trình C++ vôùi söï hoã trôï cuûa thö vieän MFC (Microsoft Foundation Class). Thö vieän naøy laø moät coâng cuï quan troïng ñeå xaây döïng nhanh caùc chöông trình öùng duïng Windows söû duïng Visual C++. Noù cuõng laøm cho vieäc laäp trình deã daøng hôn baèng caùch cung caáp nhöõng lôùp, nhöõng ñoái töôïng vôùi caùc haønh vi (Methods) vaø caùc thuoäc tính (Properties). 2.2 Thö vieän MFC: Thö vieän MFC hoã trôï 2 loaïi öùng duïng: SDI (Single Document Interface) vaø MDI (Multi Document Interface). Vôùi loaïi SDI thì ta chæ coù moät cöûa soå Windows. Döïa treân daïng taäp tin (file Document) thì chæ coù moät taäp tin ñöôïc load leân. MDI thì coù nhieàu cöûa soå con, moãi cöûa soå con naøy höôùng tôùi moät taäp tin. 2.2 .1 Window Messages: Moïi hoaït ñoäng treân FrameWork ñeàu thoâng qua thoâng ñieäp, töông öùng vôùi maõ nhaän dieän ID ta seõ coù caùc leänh töông öùng vôùi caùc thoâng ñieäp Window. Ví duï nhö ngöôøi söû duïng di chuyeån con chuoät thì cöûa soå naøy seõ nhaän ñöôïc thoâng ñieäp WM_MOUSEMOVE. Chöông trình caàn phaûi ñaùp öùng baèng moät haøm chöùc naêng töï taïo. Macro afx_msg laø nôi khai baùo haøm thaønh vieân ñaùp öùng thoâng ñieäp. Ñeå taïo haøm xöû lyù thoâng ñieäp ta söû duïng ClassWizard choïn lôùp cô sôû ñeå chöùa noù, sau ñoù choïn Window Message töông öùng sau khi ñaõ coù söï ñoàng yù thì noù ñöôïc aùnh xaï vaøo trong chöông trình. Khi ñoù ta coù theå phaùt trieån haøm xöû lyù töông öùng vôùi thoâng ñieäp ñoù. Caùc thoâng ñieäp leänh mang nhöõng haøm giaûi quyeát maëc ñònh trong MFC nhö vôùi MenuFile: New, Open, Close, Save...Edit: Clear, ClearAll, Cut...View: Toolbar, Statusbar... Thoâng ñieäp Window (baét ñaàu baèng WM_) giaûi quyeát chaän höùng thoâng ñieäp. Ngoaøi caùc thoâng ñieäp maëc ñònh, ta coù theå ñònh nghóa chuùng baèng caùch vaøo WM_USER. 2.2 .3 Hoäp thoaïi ôû cheá ñoä Modal vaø Modalless: Dialog gioáng nhö moät cöûa soå vaø noù cuõng coù theå chöùa caùc control khaùc. Ta coù theå gaùn treân noù Editboxes, Button, Listboxes, Comboboxes, Static Text, TreeView, progress indicator... hay saép xeáp cuõng nhö taïo Tab öu tieân cho töøng muïc choïn (Tab order). Visual C++ coù hai loaïi dialog laø Modal vaø Modaless nhö sau: Modal Dialog: loaïi naøy thöôøng ñöôïc duøng khi môû Dialog vaø ñôïi user ñoùng Dialog laïi neáu muoán qua cöûa soå khaùc. Khi xaây döïng xong caàn phaûi coù moät Method goïi noù. Goïi baèng haøm thaønh vieân cuûa CDialog::DoModal() ñoàng thôøi phaûi khai baùo #include “teân file header ñònh nghóa Dialog” vaøo nôi goïi noù. Modalless Dialog: Dialog ôû daïng naøy cho pheùp khoâng ñoùng Dialog khi khoâng laøm vieäc treân noù nöõa. IV. GIÔÙI THIEÄU VEÀ UML Trong thöïc teá, ñeå laøm moät döï aùn naøo ñoù ngöôøi ta thöôøng phaûi xaây döïng moâ hình tröôùc, sau ñoù môùi tieán haønh laøm theo moâ hình ñònh saün. Neáu khoâng coù moâ hình, nhöõng döï aùn ñoù thöôøng daãn ñeán nhöõng phaùt sinh ngoaøi döï kieán laøm aûnh höôûng nhieàu ñeán khaû naêng hoaøn thaønh döï aùn. Hieän nay, moät ngoân ngöõ hoã trôï vieäc leân moâ hình ñöôïc söû duïng nhieàu nhaát laø UML. Do ñoù, toâi cuõng söû duïng ngoân ngöõ naøy ñeå leân moâ hình cho döï aùn cuûa mình. 1. Toång quan: UML (Unified Modeling Languge) laø moät ngoân ngöõ moâ hình hoùa ñöôïc xaây döïng laàn ñaàu tieân bôûi Booch, Rumbaughvaø Jacobson. Noù moâ hình heä thoáng theá giôùi thöïc thaønh moät model. Moät model bao goàm moät soá View, moãi View seõ dieãn taû moät maët, moät khía caïnh cuûa heä thoáng. Noäi dung trong moät View ñöôïc moâ taû bôûi nhieàu diagram, moãi diagram bao goàm caùc Model Element nhö: class, object, note, component, relationship. Moãi element coù moät ngöõ nghóa vaø moät kyù hieäu ñoà hoïa bieåu dieãn noù. Caùc diagram cuûa UML goàm: class diagram, object diagram, activity diagram vaø deployment diagram. UML coøn coù moät soá kyõ thuaät chung ñeå theâm vaøo caùc thoâng tin khoâng theå veõ ñöôïc trong moâ hình. Caùc kyõ thuaät naøy goàm adorment ñaët caïnh element, note ñeå bieåu dieãn thoâng tin baát kyø vaø caùc thuoäc tính ñaëc bieät. Ngoaøi ra coøn caùc kyõ thuaät môû roäng goàm tagged, constraint vaø stereotype. UML khoâng chæ laø söï chuaån hoùa vaø tìm ra kyù hieäu thoáng nhaát maø noù coøn bao goàm nhöõng khaùi nieäm môùi nhö: caùch moâ taû vaø söû duïng pattern (maãu thieát keá|) trong ngoân ngöõ moâ hình hoùa, caùch söû duïng khaùi nieäm stereotype ñeå môû roäng vaø chuyeån ñoåi moâ hình… Vì vaäy, vieäc tìm hieåu UML khoâng chæ laø hieåu veà caùc bieåu töôïng vaø yù nghóa cuûa chuùng maø coøn laø hieåu veà moâ hình hoùa höôùng ñoái töôïng moät caùch thaät söï. 2. Coâng duïng cuûa UML: UML coù theå moâ hình hoùa nhieàu loaïi heä thoáng khaùc nhau. Noù coøn coù theå ñöôïc duøng trong caùc phase khaùc nhau trong quaù trình phaùt trieån heä thoáng. Muïc tieâu cuûa UML laø coù theå moâ taû ñöôïc baát kyø kieåu heä thoáng naøo theo hình thöùc caùc diagram höôùng ñoái töôïng nhö: heä thoáng thoâng tin, heä thoáng kyõ thuaät, heä thoáng phaân boá… Haàu heát caùc heä thoáng ñeàu khoâng phuø hôïp hoaøn toaøn vôùi moät trong caùc loaïi treân maø chuùng coù theå thuoäc nhieàu loaïi heä thoáng cuøng luùc. UML coù khaû naêng moâ hình hoùa taát caû caùc loaïi heä thoáng naøy. 3. Khaùi quaùt veà UML: UML bao goàm caùc thaønh phaàn sau: View: moãi view chæ ra moät maët khaùc nhau cuûa heä thoáng ñöôïc moâ hình hoùa. Moät View coù theå bao goàm nhieàu diagram. Ngoaøi ra View coøn duøng ñeå lieân keát UML vôùi caùc method/ process cuûa quaù trình phaàn meàm. Diagram: laø bieåu ñoà moâ taû noäi dung cuûa moät View. UML coù 9 loaïi diagram ñöôïc duøng keát hôïp ñeå cung caáp taát caû caùc View cuûa heä thoáng. Model element: laø caùc khaùi nieäm söû duïng trong diagram nhö class, object, message, relationship (association, dependency, generalization). Moät model element coù theå ñöôïc duøng trong nhieàu diagram. General mechanism: cung caáp caùc thoâng tin ñaëc bieät hay ngöõ nghóa veà moät model element. 3.1 View: Moät heä thoáng khoâng theå ñöôïc moâ taû heát chæ trong moät bieåu ñoà, noù neân ñöôïc moâ taû rieâng cho moãi khía caïnh khaùc. Vì vaäy, moät heä thoáng ñöôïc moâ taû bôûi moät soá View, moãi View phaûn aùnh moät maët cuûa heä thoáng. Moãi View bao goàm nhieàu diagram vaø moãi diagram cuõng coù theå thuoäc caùc View khaùc nhau. Moät diagram chöùa caùc kyù hieäu ñoà hoïa bieåu dieãn model element cuûa heä thoáng. Caùc View cuûa UML laø: Use-case view: chæ ra caùc chöùc naêng cuûa heä thoáng ñoái vôùi caùc actor beân ngoaøi. Logical view: chæ ra caùc chöùc naêng ñöôïc thieát keá nhö theá naøo trong heä thoáng. Component view: chæ ra caùch toå chöùc cuûa code component. Concurrency view: giaûi quyeát vaán ñeà lieân laïc vaø ñoàng boä ñöôïc bieåu dieãn trong moät heä thoáng ñoàng thôøi. Deployment view: chæ vieäc trieån khai heä thoáng ra kieán truùc vaät lyù qua caùc node (maùy tính vaø thieát bò). 3.2 Diagram: Diagram laø bieåu ñoà chæ söï saép xeáp caùc kyù hieäu model element nhaèm minh hoïa moät phaàn hoaëc moät khía caïnh cuûa heä thoáng. Moät moâ hình heä thoáng thöôøng coù moät soá loaïi diagram. Moät diagram phaûi laø moät phaàn cuûa moät view naøo ñoù vaø noù cuõng coù theå thuoäc nhieàu view khaùc. UML coù 9 loaïi diagram laø : Use-case diagram. Class diagram. Object diagram. State diagram. Sequence diagram. Collaboration diagram. Activity diagram. Component diagram. Deployment diagram. Do ñaëc thuø cuûa ñeà taøi laø moâ phoûng quaù trình nhaän thöùc theá giôùi xung quanh ñeå tìm kieám neân moät soá diagram sau ñöôïc söû duïng: Class diagram – xaây döïng caáu truùc tónh cuûa caùc lôùp trong öùng duïng Sequence diagram – leân löôïc ñoà cho quaù trình nhaän thöùc Collaboration diagram – löôïc ñoà töông taùc cuûa caùc ñoái töôïng trong öùng duïng Activity diagram – leân löôïc ñoà cho quaù trình tìm kieám Class diagram Class diagram chæ ra caáu truùc tónh cuûa caùc class trong heä thoáng. Caùc class bieåu dieãn nhöõng gì xöû lyù trong heä thoáng. Caùc class coù theå lieân quan vôùi nhau theo moät soá quan heä nhö sau: Associate: noái ñeán class khaùc Dependent: moät class thuoäc/ söû duïng moät class khaùc. Speciallize: moät class laø moät ñaëc bieät hoùa cuûa moät class khaùc. Package: nhoùm chung trong moät ñôn vò. Moät heä thoáng thöôøng coù moät soá class diagram. Moät class cuõng coù theå tham gia vaøo nhieàu class diagram khaùc nhau. Collaboration diagram Collaboration diagram bieåu dieãn söï coäng taùc cuûa caùc object trong heä thoáng. Collaboration diagram chæ söï trao ñoåi message (ñöôïc goïi laø interaction), noù coøn bieåu dieãn caùc object vaø caùc quan heä cuûa chuùng (ñöôïc goïi laø ngöõ caûnh). Ngoaøi ra , collaboration diagram coøn coù moät chöùc naêng quan troïng laø bieåu dieãn caùc active object. Caùc active object coù theå cuøng thöïc thi ñoàng thôøi do ñoù chuùng ñöôïc duøng trong vieäc bieåu dieãn heä thoáng coù söï thöïc thi ñoàng thôøi. Sequence diagram. Sequence diagram chæ söï coäng taùc giöõa moät soá object. Noù ñöôïc söû duïng ñeå xaùc ñònh trình töï göûi message giöõa caùc object cuõng nhö söï töông taùc giöõa caùc object. Sequence diagram goàm caùc object ñöôïc xeáp theo ñöôøng ngang, noù chæ söï trao ñoåi message giöõa caùc object theo thôøi gian (thôøi gian troâi qua theo höôùng ñi xuoáng). Message ñöôïc bieåu dieãn nhö moät ñöôøng muõi teân noái caùc object vôùi caùc ñaëc taû veà thôøi gian coù theå theâm vaøo beân leà diagram. Do sequence diagram vaø collaboration diagram khaù gioáng nhau neân vieäc choïn löïa söû duïng diagram naøo ñöôïc xaùc ñònh nhö sau: Neáu muoán nhaán maïnh yeáu toá thôøi gian hay trình töï thöïc hieän thì ta söû duïng sequence diagram coøn neáu muoán nhaán maïnh ngöõ caûnh thì ta choïn collaboration diagram. Activity diagram Activity diagram chæ doøng coâng vieäc maø heä thoáng caàn thöïc hieän. Activity diagram chuù troïng vaøo keát quaû coâng vieäc do ñoù noù ñöôïc duøng trong vieäc moâ taû use-case hay interaction. Activity diagram bao goàm nhieàu action state vaø moãi action state chöùa ñaëc taû veà moät haønh ñoäng (action) caàn ñöôïc thöïc hieän. Moät action state seõ thoaùt khoûi state sau khi noù thöïc hieän action. Activity diagram coøn coù theå chæ ra söï thöïc thi song song cuûa caùc action state cuõng nhö ñaëc taû veà thoâng ñieäp truyeàn nhaän. 3.3 Model Elements: Caùc khaùi nieäm söû duïng trong diagram ñöôïc goïi laø model element. Moãi model element coù moät view element töông öùng maø noù laø kyù hieäu ñoà hoïa ñeå bieåu dieãn element trong diagram. Moät model element coù theå xuaát hieän trong nhieàu diagram khaùc nhau. Moät soá loaïi model element laø: class, object, package, component, use case, note, interface, state… Relationship (quan heä) laø moät loaïi model element duøng ñeå keát noái giöõa caùc model element nhaèm bieåu thò moái quan heä giöõa chuùng vôùi nhau. Caùc loaïi relationship goàm: Association (keát hôïp): noái caùc element vaø lieân keát caùc instance cuûa chuùng. Generalization (toång quaùt hoùa): coøn goïi laø quan heä thöøa keá, nghóa laø moät element coù theå laø ñaëc taû cuûa moät element khaùc. Dependency (phuï thuoäc): chæ ra raèng moät element phuï thuoäc vaøo moät element khaùc theo moät nghóa naøo ñoù. Aggregation: moät hình thöùc cuûa association, trong ñoù moät element chöùa moät element khaùc. Caùc model element khaùc coøn coù message, action, stereotype… 3.4 Tool: Vieäc söû duïng moät ngoân ngöõ moâ hình hoùa phöùc taïp nhö UML ñoøi hoûi phaûi coù moät coâng cuï hoã trôï. Coâng cuï naøy ñöôïc goïi laø Modeling tool hay Case tool, chaúng haïn nhö Rational Rose laø moät Case tool. Moät Case tool hieän ñaïi caàn cung caáp ñöôïc caùc chöùc naêng sau: Veõ diagram: tool phaûi hoã trôï cho vieäc bieåu dieãn caùc diagram trong ngoân ngöõ. Noù cuõng phaûi coù theå hieåu ñöôïc muïc ñích cuûa diagram, bieát ñöôïc caùc semantic (ñaëc taû ngöõ nghóa) vaø rule ñôn giaûn. Nhö moät nôi löu tröõ: tool phaûi hoã trôï moät nôi löu tröõ chung cho caùc thoâng tin trong moâ hình. Neáu teân cuûa moät class bò thay ñoåi trong moät diagram thì thay ñoåi naøy cuõng seõ ñöôïc phaûn aùnh ôû caùc diagram khaùc coù söû duïng class naøy. Hoã trôï navigation: tool coù theå deã daøng doø tìm moät element töø diagram naøy sang diagarm khaùc. Hoã trôï multiuser: tool phaûi hoã trôï nhieàu ngöôøi söû duïng, cho pheùp hoï cuøng laøm vieäc treân moät moâ hình maø khoâng bò aûnh höôûng laãn nhau. Phaùt sinh code: thoâng tin trong moâ hình ñöôïc chuyeån thaønh khung maõ chöông trình, laøm cô sôû cho giai ñoaïn caøi ñaët. Reverse engineer: khaû naêng ñoïc code vaø sinh ra moâ hình töø noù. Tích hôïp vôùi caùc tool khaùc: tool phaûi coù khaû naêng tích hôïp vôùi caùc tool khaùc caû veà moâi tröôøng phaùt trieån nhö editor, compiler, debugger cuõng nhö caùc enterprise tool khaùc nhö configuration management vaø version control system. Bao phuû moïi möùc tröøu töôïng cuûa moâ hình: tool phaûi deã daøng truy tìm töø möùc moâ taû cao nhaát cuûa heä thoáng xuoáng ñeán möùc code. Trao ñoåi moâ hình: moät moâ hình hay diagram trong moâ hình coù theå ñöôïc ñem töø moät tool naøy sang tool khaùc ñeå söû duïng. CHÖÔNG III: HÖÔÙNG TIEÁP CAÄN CUÛA ÑEÀ TAØI Vôùi muïc ñích laø moâ phoûng Robot trong theá giôùi thöïc neân ñeà taøi söû duïng moät soá höôùng tieáp caän sau: Camera toång hôïp: öùng duïng kyõ thuaät Camera toång hôïp ñeå taïo ra khung nhìn cho Robot. Ñaây laø moät kyõ thuaät raát phöùc taïp trong ñoà hoïa 3D neân trong giôùi haïn cuûa ñeà taøi toâi chæ vaän duïng tính chaát meàm deûo cuûa Camera toång hôïp ñeå moâ phoûng theá giôùi 2D nhö sau: Con maét ñaët ôû vò trí ñöùng cuûa Robot. Cöûa soå quan saùt laø moät ñoaïn thaúng coù theå xoay 8 höôùng xung quanh Robot. Taàm nhìn cuûa Robot coù theå ñöôïc thay ñoåi ñeå thu thaäp caùc thoâng tin mong muoán. Kyõ thuaät xeùn: Trong thöïc teá, taàm nhìn cuûa Robot coù theå ñöôïc xem nhö laø xa voâ haïn. Vì tín hieäu lieân tuïc ñöôïc truyeàn ñeán thieát bò nhaän cuûa Robot neân Robot chæ caàn phaân tích caùc tín hieäu ñoù laø ñaõ coù thoâng tin veà moâi tröôøng. Ñöùng veà maët laäp trình thì khi taàm nhìn cuûa Robot caøng xa thì khoái löôïng coâng vieäc phaûi xöû lyù caøng nhieàu. Do muïc tieâu cuûa ñeà taøi naøy laø moâ phoûng caùch nhaän thöùc cuûa Robot ñeå traùnh neù neân ta khoâng caàn cho Robot coù taàm nhìn xa. Vì theá kyõ thuaät xeùn ñöôïc duøng ôû ñaây ñeå giôùi haïn taàm nhìn cuûa Robot. Kyõ thuaät xeùn ñöôïc duøng keát hôïp vôùi Camera toång hôïp nhaèm giaûi quyeát baøi toaùn moâ phoûng caùch nhìn cuûa Robot nhö sau: Ñaàu tieân ta taïo moät khung nhìn cho Robot (baèng caùch söû duïng tieáp caän Camera toång hôïp) Sau ñoù ta duøng giaûi thuaät xeùn ñeå laáy thoâng tin veà caùc ñoái töôïng naèm trong khung nhìn cuûa Robot. Nguyeân taéc xeùn: Aùp duïng giaûi thuaät toâ maøu treân khoâng gian tìm kieám theo khung nhìn cuûa Robot (ñöôïc taïo ra bôûi phöông phaùp Camera toång hôïp) ñeå laáy thoâng tin veà nhöõng ñoái töôïng trong khoâng gian tìm kieám loït vaøo khung nhìn naøy. Caùc kyõ thuaät tìm kieám Heristic: Ñeà taøi söû duïng 2 kyõ thuaät tìm kieám cuûa trí tueä nhaân taïo laø leo ñoài vaø A*. Tuy coù nhieàu höôùng tieáp caän vôùi phöông phaùp leo ñoài nhöng hieän taïi coù 2 höôùng chính laø leo ñoài khoâng quay lui vaø leo ñoài coù keát hôïp quay lui. Trong ñeà taøi naøy, em söû duïng höôùng tieáp caän coù quay lui vì noù phuø hôïp vôùi yù ñoà thieát keá cuûa baøi toaùn naøy. Coøn kyõ thuaät tìm kieám A*, do thôøi gian quaù haïn cheá neân em khoâng caøi ñaët kòp. Tuy nhieân ñaây coù theå laø moät höôùng môû roäng, khi coù ñuû thôøi gian vaø ñieàu kieän em seõ tieáp tuïc thöïc hieän noù. CHÖÔNG IV: GIAO DIEÄN CUÛA ÖÙNG DUÏNG Taêng giaûm soá löôïng vaät caûn Taêng giaûm kích thöôùc khoâng gian tìm kieám Giao dieän cuûa chöông trình minh hoïa luùc khôûi ñoäng ñöôïc thieát keá nhö sau: Stone: ñaïi dieän cho vaät caûn treân ñöôøng ñi cuûa Robot Robot Treasure: ñaïi dieän vaät caàn tìm Chuù thích: Start/Stop search: baét ñaàu hoaëc ngöng chöùc naêng tìm kieám Pause/Resume: taïm döøng hoaëc tieáp tuïc quaù trình tìm kieám Close: ñoùng öùng duïng Show view: baät/ taét khung nhìn cuûa Robot Show Detail: baät/ taét baûng thoâng tin chi tieát veà Robot Radius: taêng giaûm baùn kính khung nhìn Delay time: taêng giaûm thôøi gian delay giöõa 2 böôùc ñi cuûa Robot Found Objects: hieån thò soá object trong khung nhìn cuûa Robot Giao dieän cuûa chöông trình minh hoïa luùc chaïy nhö sau: Ñöôøng Robot ñaõ ñi qua Khung nhìn cuûa Robot Baûng thoâng tin chi tieát cuûa Robot PHAÀN II : THIEÁT KEÁ CHÖÔNG TRÌNH 1. Thieát keá möùc quan nieäm: ÔÛ möùc quan nieäm ta chæ quan taâm ñeán caùc lôùp chính vaø söï töông taùc giöõa chuùng vôùi nhau. 1.1 Sô ñoà lôùp vôùi caùc lôùp chính: Moâ taû: Sô ñoà coù 5 lôùp chính vôùi yù nghóa nhö sau: Lôùp Object2D laø maãu cuûa caùc ñoái töôïng 2D nhö Robot, Stone vaø Treasure. Treân ñoù ñònh nghóa chöùc naêng xöû lyù thoâng ñieäp (ñeå nhaän bieát moät ñoái töôïng thuoäc loaïi naøo) cuõng nhö caùc ñaëc tính chung maø moïi ñoái töôïng 2D ñeàu coù nhö vò trí (position), maøu saéc (color), … . ÔÛ ñaây Stone ñaïi dieän cho vaät caûn trong moâi tröôøng (coù theå laø soâng, suoái, ñaù, röøng caây, …). Treasure ñaïi dieän cho ñoái töôïng maø Robot caàn tìm (chaúng haïn nhö kho baùu). Lôùp Robot, Stone vaø Treasure ñeàu thuoäc loaïi Object2D trong ñoù Robot vôùi nhieäm vuï chính laø tìm kieám muïc tieâu thoûa maõn yeâu caàu cuûa chuùng ta. Ñeå Robot coù theå tieáp caän muïc tieâu cuõng nhö nhaän thöùc ñöôïc moâi tröôøng xung quanh, ta trang bò cho noù moät camera (thuoäc lôùp Camera). 1.2 Bieåu ñoà coäng taùc: YÙ nghóa: Robot töông taùc vôùi caùc ñoái töôïng trong moâi tröôøng baèng caùch söû duïng moät Camera ñeå quan saùt caùc ñoái töôïng xung quanh. Caùc ñoái töôïng trong moâi tröôøng coù theå xöû lyù caùc thoâng ñieäp do Robot göûi ñeán. Cuï theå laø Robot phaùt tín hieäu ñeán caùc ñoái töôïng vaø nhaän caùc thoâng tin phaûn hoài ñeå xaùc ñònh ñoái töôïng laø Stone hay Treasure … . 2. Thieát keá möùc caøi ñaët: Nhöõng khoù khaên gaëp phaûi vaø höôùng giaûi quyeát khi chuyeån töø yù töôûng sang caøi ñaët: Ñeå bieát ñöôïc caùc ñoái töôïng naøo loït vaøo khung nhìn cuûa Robot ta phaûi coù saün moät taäp caùc ñoái töôïng (toïa ñoä cuûa chuùng khoâng choàâng leân nhau). Caùc ñoái töôïng naøy do chöông trình kieåm soaùt vaø chöông trình khoâng cung caáp heát thoâng tin veà moïi ñoái töôïng cho Robot maø chæ cung caáp thoâng tin veà nhöõng ñoái töôïng naøo loït vaøo khung nhìn. Ñeå giaûi quyeát vaán ñeà naøy ta taïo ra moät loaïi ñoái töôïng taïm goïi laø Controller vôùi chöùc naêng laø quaûn lyù caùc ñoái töôïng vaø cung caáp thoâng tin veà nhöõng ñoái töôïng naøo loït vaøo khung nhìn cuûa Robot. Robot khoâng bieát ñeán söï coù maët cuûa Controller. Ñeå giaûi quyeát vaán ñeà naøy ta coi nhö Camera bieát coù Controller vôùi yù nghóa laø noù coù theå yeâu caàu thoâng tin veà ñoái töôïng trong vuøng nhìn töø Controller. Robot coù theå ñi vaøo nhöõng ñöôøng khoâng ñi tieáp ñöôïc. Do ñoù coù nhöõng luùc noù phaûi quay lui. Ñeå giaûi quyeát vaán ñeà quay lui ta buoäc phaûi löu veát ñöôøng ñi. Theo nguyeân taéc laäp trình höôùng ñoái töôïng thì taát caû ñeàu laø ñoái töôïng. Trong ñeà taøi naøy, ñöôøng ñi ñöôïc hình thaønh töø caùc khoaûng troáng cho neân ta taïo ra moät lôùp Empty ñaïi dieän cho caùc ñoái töôïng khoaûng troáng. Vieäc ta taïo ñoái töôïng khoaûng troáng cuõng khoâng coù gì laø sai bôûi leõ khoaûng troáng cuõng chöùa thoâng tin (troáng ôû ñaâu) vaø cuõng coù khaû naêng xöû lyù thoâng ñieäp (khoâng phaûn hoài thoâng tin – trong caøi ñaët ta cho noù phaûn hoài veà NULL). 2.1 Sô ñoà lôùp: Vôùi yeâu caàu cuûa ñeà taøi, sô ñoà lôùp ñöôïc thieát keá nhö sau: Moái quan heä giöõa caùc lôùp: Robot coù moät Camera, lôùp Camera coù moät CameraView vaø lôùp Camera naøy bieát coù moät Controller. Lôùp Controller naøy quaûn lyù moät taäp caùc ñoái töôïng Object2D goàm Treasure, Stone vaø Empty. YÙ nghóa: Robot thu thaäp thoâng tin baèng caùch yeâu caàu Camera chuïp hình vaø gôûi veà moät taäp caùc ñoái töôïng loït vaøo khung nhìn. Camera coù ñöôïc thoâng tin veà ñoái töôïng baèng caùch taïo moät khung nhìn (CameraView) vaø gôûi yeâu caàu cho Controller ñeå coù ñöôïc caùc ñoái töôïng loït vaøo khung nhìn. Controller seõ thöïc hieän vieäc xeùn döïa vaøo khung nhìn ñeå laáy caùc ñoái töôïng trong khung nhìn traû veà cho Camera. Khi ñoù Camera seõ göûi thoâng tin naøy cho Robot. Nhö vaäy, ta coù theå noùi raèng Robot chöa bieát thoâng tin veà söï xuaát hieän cuûa caùc ñoái töôïng trong moâi tröôøng maø phaûi ñi ñeán ñaâu môùi bieát ñeán ñoù. Cô cheá phaûn hoài thoâng tin cuûa caùc ñoái töôïng trong moâi tröôøng: Trong thöïc teá, ta truyeàn thoâng ñieäp baèng caùch phaùt tín hieäu, ví duï nhö chieáu baèng tia saùng, vaø nhaän thoâng tin phaûn hoài laø quang phoå cuûa ñoái töôïng. Döïa vaøo quang phoå cuûa ñoái töôïng ta coù theå xaùc ñònh ñoái töôïng thuoäc loaïi naøo. Trong phaïm vi cuûa ñeà taøi naøy, ta khoâng caøi ñaët theâm lôùp chuyeân veà phaân tích quang phoå maø ta cho caùc ñoái töôïng phaûn hoài thoâng ñieäp laø loaïi cuûa ñoái töôïng. Chæ coù moät tröôøng hôïp ñaëc bieät laø caùc ñoái töôïng Empty khoâng phaûn hoài thoâng tin (traû veà NULL). Khi ñoù, döïa vaøo thoâng tin phaûn hoài ta coù theå bieát ñöôïc ñoái töôïng thuoäc loaïi naøo (Empty hay Non-Empty). Thöïc teá laø coù khaû naêng coù nhöõng ñoái töôïng môùi maø ta chöa coù thoâng tin veà quang phoå. Trong caøi ñaët neáu gaëp nhöõng ñoái töôïng môùi ta coi nhö noù cuõng laø vaät caûn. 2.2 Sô ñoà coäng taùc: Toaøn boä quaù trình töông taùc ñöôïc thöïc hieän thoâng qua caùc phöông thöùc sau cuûa Robot: void MyRobot::getObjectInfo() { getNextDir(); //xaùc ñònh höôùng quan saùt unsigned char tmp = searchDir(curDirPos.x, curDirPos.y); if(((tmp ^ searchedDir) & tmp) == tmp){ updateSearchDir(tmp); ObjectList* objectsInView = camera.ViewableObjects(MessageInfo::CreateMessageInfo(this, NULL)); if(objectsInView != NULL){ #ifdef _DEBUG CString size; size.Format("%d\r\n", objectsInView->getSize()); *controller.msObjects += size; controller.dlg->UpdateData(FALSE); #endif objectsInView->foreach(this, updateInfo); delete objectsInView; } } } void updateInfo(void* info, void* val){ // haøm friend cuûa lôùp MyRobot. MyRobot* RB = (MyRobot*)info; Object2D* obj = (Object2D*)val; eObjectType* objType = (eObjectType*)obj->handleMsg(NULL); eObjectType* oldType = &RB->objectInfo[obj->position.y][obj->position.x]; if(*oldType != UNKNOWN) return; if(objType == NULL) //gaëp khoaûng troáng *oldType = EMPTY; else switch(*objType){ case TREASURE: RB->predictedPos = obj->position; RB->found = true; *oldType = EMPTY; //coù theå ñi ñöôïc break; case STONE: *oldType = STONE; break; default: *oldType = UNKNOWN; } //ñeán nôi döï ñoaùn nhöng chöa gaëp if(RB->predictedPos == obj->position && (objType == NULL || RB->found == false)) RB->GetNewPredictPos(); //ñoaùn ñieåm khaùc } extern Controller controller; ObjectList* Camera::ViewableObjects(MessageInfo* info) { return controller.ObjectsInView(this->CreateView()); } 2.3 Caáu truùc cuûa lôùp Robot: Caùc thuoäc tính: objectInfo: maûng 2 chieàu vôùi soá phaàn töû toái ña Robot coù theå löu tröõ thoâng tin veà loaïi ñoái töôïng cuõng nhö ñeå tìm kieám. predictedPos: vò trí döï ñoaùn hieän taïi. searchedDir: caùc höôùng ñaõ quan saùt ôû vò trí hieän taïi. maxSearchDir: höôùng quan saùt toái ña coù theå coù. Caùc phöông thöùc: Caùc phöông thöùc public: Init: void MyRobot::Init(CPoint p) { searchPath.clear(); setPosition(p); *controller.msObjects = ""; } StartSearch: void MyRobot::StartSearch() { m_bSearching = true; bNoReplay = false; *dlgObjects.msObjects = ""; resetObjectInfo(); camera.directionPos = &curDirPos; getObjectInfo(); } Search: void MyRobot::Search() { if(IsFound()) return; if(!canGo()){ if(searchedDir >= maxSearchDir){ if(!canReturn()) bNoReplay = true; } } if(!IsFound()) getObjectInfo(); if(pFunc != NULL) pFunc(objectInfo); } SetPosition: void MyRobot::setPosition(CPoint p) { objectInfo[p.y][p.x] = PASSED; position = p; searchPath.add(new PositionInfo(&position, searchedDir)); searchedDir = 0; gotoPosition(p); } Caùc phöông thöùc noäi boä: canGo: bool MyRobot::canGo() { CPoint p; bool bGo = false; depth = camera.radius; do{ --depth; PriorityQueue* ways = waysAtPos(position); while(!ways->isEmpty()){ Position_Data* pd = ways->remove(); p = pd->pos; delete pd; if(canGoTo(p)){ setPosition(p); bGo = true; break; } } delete ways; }while(!bGo && depth > 0); return bGo; } canGoTo: bool MyRobot::canGoTo(CPoint q) { int x = q.x - position.x; int y = q.y - position.y; if((x & y) != 0){// goùc 1/8 CPoint p[3]; //tính hai ñieåm keà döïa vaøo vò trí vaø höôùng posFromDirect(x, y, p); //caám vöôït qua khe heïp if(cannotGoto(p[1]) && cannotGoto(p[2])) return false; } int ret = (depth > 0 ? tryFind(q, depth) : (objectInfo[q.y][q.x] == EMPTY ? 1 : 0)); return (ret >= depth); } tryFind: int MyRobot::tryFind(CPoint p, int n) { if(n < 1 || objectInfo[p.y][p.x] == STONE) return 0; CPoint p1(p); p1.x += deltaX(p1); p1.y += deltaY(p1); eObjectType type = objectInfo[p1.y][p1.x]; if(type == EMPTY || type == PASSED) return 1 + tryFind(p1, n - 1); else return 0; } canReturn: bool MyRobot::canReturn() { bool bReturn = false; PositionInfo* pInfo = searchPath.get(); if(pInfo != NULL){ searchPath.remove(); delete pInfo; pInfo = searchPath.get(); if(pInfo != NULL){ returnTo(pInfo); bReturn = true; } } return bReturn; } waysAtPos: PriorityQueue* MyRobot::waysAtPos(CPoint p) { static int dir[] = {-1, -1, 0, -1, 1, -1, 1, 0, 1, 1, 0, 1, -1, 1, -1, 0}; PriorityQueue* ways = new PriorityQueue(); for(int i = 0; i < 16; ){ int x = dir[i++]; int y = dir[i++]; CPoint p1(p); p1.x += x; p1.y += y; if(p1.x >= 0 && p1.x = 0 && p1.y < HEIGHT && objectInfo[p1.y][p1.x] == EMPTY){ int pr = (abs(p1.x - predictedPos.x) + abs(p1.y - predictedPos.y)); ways->add(&p1, pr); } } return ways; } deltaX: int MyRobot::deltaX(CPoint p) { int x = 0; if(p.x > predictedPos.x) x = -1; else if(p.x < predictedPos.x) x = 1; return x; } deltaY: int MyRobot::deltaY(CPoint p) { int y = 0; if(p.y > predictedPos.y) y = -1; else if(p.y < predictedPos.y) y = 1; return y; } 2.4 Sô ñoà lôùp vôùi caùc thuoäc tính: Object2D: position: vò trí hieän taïi cuûa ñoái töôïng. Ñeå taêng toác ñoä thöïc thi, ôû ñaây ta cho noù laø public vôùi yù nghóa laø coù theå laáy thoâng tin tröïc tieáp maø khoâng phaûi goïi phöông thöùc getPosition. Tuy nhieân, ñeå thieát laäp vò trí ta neân goïi phöông thöùc setPosition neáu khoâng thì chöông trình coù theå chaïy sai so vôùi yù muoán. color: maøu saéc cuûa ñoái töôïng. Camera: Taát caû caùc thuoäc tính ñeàu laø public vì nhö theá Robot deã thao taùc hôn maø khoâng phaûi goïi caùc phöông thöùc get vaø set. bShow: hieän khung nhìn. position: chính laø vò trí cuûa Robot. directionPos: moät trong 8 höôùng nhìn cuûa Robot. angle: phaân nöûa goùc nhìn cuûa khung nhìn. radius: baùn kính taàm nhìn. CameraView: Ñeå ñôn giaûn hoaù vaán ñeà ta coi nhö khung nhìn coù hình tam giaùc caân vôùi ñænh laø vò trí cuûa Robot. position[4]: 3 ñænh tam giaùc vaø 1 ñieåm laø trung ñieåm caïnh ñaùy. Controller: m_bHasObjects: Controller coù ñoái töôïng ñeå quaûn lyù. 2.5 Sô ñoà tìm kieám: Giaûi thích: Init State: khôûi taïo moät soá thoâng soá cuûa quaù trình tìm kieám. Ready: Traïng thaùi saün saøng (coù khaû naêng gaëp ñoái töôïng caàn tìm). Ready1: Traïng thaùi saün saøng (khoâng coù khaû naêng gaëp ñoái töôïng caàn tìm). Found?: coù gaëp (ñi ñeán) ñoái töôïng caàn tìm chöa? Update Heuristic: Hoïc (löu thoâng tin veà vò trí cuûa ñoái töôïng caàn tìm) CanGo?: coù theå ñi ñöôïc (xung quanh noù coù ít nhaát moät khoaûng troáng chöa ñi qua)? Go: ñi moät böôùc (theo höôùng ñi ñöôïc) AllDirSearched?: Taát caû caùc höôùng coù theå quan saùt ñeàu ñaõ quan saùt? CanReturn?: Coù theå quay lui (danh saùch ñieåm ñaõ ñi khoâng roãng)? Return: quay lui moät böôùc (ñeán nôi tröôùc ñoù, xoùa ñieåm hieän taïi khoûi danh saùch ñieåm ñaõ ñi). GetDirectionInfo: Xaùc ñònh höôùng naøo caàn quan saùt tieáp. GetViewableObject: Caùc ñoái töôïng naøo loït vaøo khung nhìn ñang quan saùt. UpdateSearchedInfo: caäp nhaät thoâng tin veà höôùng ñaõ quan saùt. UpdateStateInfo: Caäp nhaät thoâng tin veà caùc ñoái töôïng ñaõ bieát. 2.6 Sô ñoà tuaàn töï cho chöùc naêng thu thaäp thoâng tin (chöùc naêng nhaän thöùc): Robot göûi yeâu caàu ñeán Camera vôùi thoâng tin veà vò trí, höôùng nhìn. Camera döïa vaøo thoâng tin coù ñöôïc seõ taïo CameraView, göûi thoâng tin veà view naøy cho Controller ñeå yeâu caàu danh saùch caùc ñoái töôïng trong view; Thoâng tin coù ñöôïc töø Controller seõ ñöôïc göûi traû veà cho Robot. Controller khi nhaän ñöôïc thoâng ñieäp seõ thöïc hieän loïc caùc ñoái töôïng naøo loït vaøo trong view (xeùn hình chöõ nhaät - ma traän chöùa ñoái töôïng - vaøo ña giaùc) vaø göûi thoâng tin veà nhöõng ñoái töôïng ñoù veà cho Camera (cuï theå laø danh saùch chöùa caùc con troû chæ ñeán caùc ñoái töôïng). Caùc ñoái töôïng vaãn do Controller kieåm soaùt (ñuùng hôn laø duø caùc ñoái töôïng coù dôøi ñi ñaâu ñi chaêng nöõa Controller vaãn luoân coù ñòa chæ cuûa chuùng mieãn laø chuùng coøn soáng – ta khoâng delete chuùng). Döïa vaøo danh saùch caùc ñoái töôïng coù ñöôïc töø Camera, Robot seõ laàn löôït phaân tích thoâng tin veà loaïi ñoái töôïng (baèng caùch göûi thoâng ñieäp ñeán caùc ñoái töôïng vaø nhaän thoâng tin phaûn hoài) ñeå xaùc ñònh caùc loaïi ñoái töôïng naøo loït vaøo khung nhìn (caäp nhaät thoâng tin veà loaïi ñoái töôïng). 2.7 Caùc lôùp tieän ích: Giaûi thích: Caáu truùc sData ñöôïc duøng ñeå chöùa thoâng tin kieåu T (moät loaïi lôùp chöa bieát). Noù coù con troû next coù theå troû ñeán kieåu sData. Lôùp sData laø lôùp chuyeân bieät cuûa lôùp sData vôùi thoâng tin veà kieåu laø T. Lôùp CStack laø stack duøng ñeå chöùa caùc ñoái töôïng thuoäc kieåu T. Noù coù moät con troû tail thuoäc kieåu sData. Lôùp CStack laø lôùp chuyeân bieät cuûa lôùp CStack vôùi thoâng tin veà kieåu laø Object2D. Lôùp ObjectList duøng stack ñeå chöùa caùc ñoái töôïng Object2D. Noù coù moät con troû list thuoäc kieåu CStack. Lôùp CStack laø lôùp chuyeân bieät cuûa lôùp CStack vôùi thoâng tin veà kieåu laø PositionInfo. Lôùp PositionInfoList duøng stack ñeå chöùa caùc ñoái töôïng PositionInfo. Noù coù moät con troû list thuoäc kieåu CStack. Haøng ñôïi öu tieân: Giaûi thích: Lôùp PriorityQueue duøng ñeå chöùa caùc höôùng ñi coù theå coù cuûa Robot töø vò trí hieän taïi vôùi ñoä öu tieân döïa vaøo ñoä leäch so vôùi ñieåm döï ñoaùn. Noù coù moät con troû items duøng ñeå troû ñeán phaàn töû ñaàu tieân cuûa danh saùch öu tieân. Moãi phaàn töû cuûa danh saùch öu tieân chöùa vò trí, ñoä öu tieân vaø moät con troû next ñeå troû ñeán phaàn töû keá tieáp trong danh saùch. Phaàn töû cuoái cuøng seõ khoâng troû ñeán ñaâu caû (troû ñeán NULL). Phöông thöùc remove ñöôïc duøng ñeå laáy phaàn töû ñaàu khoûi danh saùch (phaàn töû keá tieáp neáu coù seõ laø phaàn töû ñaàu cuûa danh saùch). Phöông thöùc add duøng ñeå theâm moät phaàn töû (coù thoâng tin veà vò trí vaø ñoä öu tieân) vaøo danh saùch ôû vò trí thích hôïp. Trong tröôøng hôïp coù nhieàu phaàn töû cuøng ñoä öu tieân thì traät töï cuûa chuùng laø ngaãu nhieân. KEÁT LUAÄN VAØ HÖÔÙNG MÔÛ ROÄNG Sau moät thôøi gian thöïc hieän, ñeán nay ñeà taøi cô baûn ñaõ hoaøn thaønh nhieäm vuï ñöôïc giao. Cuï theå laø phaàn tìm hieåu coâng ngheä, em ñaõ vaän duïng caùc coâng ngheä ñöôïc yeâu caàu vaøo ñeà taøi vaø chöông trình öùng duïng minh hoïa veà cô baûn ñaõ hoaøn thaønh. Tuy nhieân, do trình ñoä chuyeân moân cuõng nhö kinh nghieäm coøn haïn cheá neân vieäc öùng duïng caùc coâng ngheä vaøo ñeà taøi chöa thaät söï toát laém. Cuï theå laø kyõ thuaät Camera toång hôïp chöa ñöôïc phaùt huy heát khaû naêng maø ñeà taøi chæ coù theå söû duïng ñöôïc moät ít tính naêng cuûa noù. Beân caïnh ñoù, vieäc vaän duïng caùc kyõ thuaät cuûa trí tueä nhaân taïo vaøo ñeà taøi cuõng coøn nhieàu haïn cheá neân chöa theå laøm cho Robot coù khaû naêng thoâng minh cao. Caùc höôùng caàn ñöôïc môû roäng cuûa ñeà taøi laø: Vaän duïng toát hôn tieáp caän Camera toång hôïp vaøo quaù trình nhaän thöùc ñeå vieäc moâ phoûng khaû naêng “nhìn” cuûa Robot thöïc teá hôn. Khaû naêng hoïc cuûa Robot caàn ñöôïc caûi thieän ñeå Robot coù theå “thoâng minh” hôn trong vieäc tìm kieám nhö traùnh neù chöôùng ngaïi vaät, choïn höôùng ñi toát, döï ñoaùn vò trí cuûa vaät caàn tìm chính xaùc hôn…. Trong töông lai, khi coù ñuû thôøi gian, nhaân löïc cuõng nhö coâng ngheä thì em hy voïng ñeà taøi naøy seõ ñöôïc phaùt trieån hoaøn thieän hôn nöõa ñeå coù theå trôû thaønh moät coâng cuï ñaéc löïc trong vieäc thieát keá Robot .