Đề tài Xây dựng mô hình mô phỏng một đối tượng – tạm gọi là Robot – có khả năng nhận thức môi trường chung quanh để tìm kiếm mục tiêu

PHẦN I : LÝ THUYẾT CHƯƠNG I : Ý TƯỞNG VÀ ĐẶC TRƯNG CỦA BÀI TOÁN & 1. Ýù Tưởng Trong thời đại kỹ thuật công nghệ phát triển mạnh mẽ như hiện nay, vấn đề tự động hoá luôn được đặt lên vị trí hàng đầu. Những công việc trước đây con người phải tự tay làm thì ngày nay đã được thay thế dần bằng những bộ máy hiện đại được lập trình theo những chức năng chuyên dụng. Theo đà phát triển, con người đã chế tạo ra Robot – một loại máy móc thông minh kết hợp từ các ngành cơ khí, điện tử và tin học – và nó giúp con người rất nhiều việc: từ việc thám hiểm những nơi con người không đến được cho đến những công việc nội trợ trong gia đình. Từ khi xuất hiện đến nay, Robot luôn được các nhà khoa học đặc biệt quan tâm và làm cho nó ngày càng thông minh hơn, chuyên nghiệp hơn để thích ứng với những yêu cầu mới, những công việc mới trong những lĩnh vực mới. Một trong những việc rất cần đến sự trợ giúp của Robot là lĩnh vực tìm kiếm, chẳng hạn như việc tìm và gỡ mìn, một việc làm rất nguy hiểm đối với con người nhưng Robot lại làm rất tốt. Bên cạnh đó, việc thám hiểm những hành tinh xa xôi, những đáy biển sâu… thì không có sự lựa chọn nào tốt hơn Robot. Hiện nay, con người còn có những ý tưởng chưa thực hiện được về việc chế tạo Robot như: Robot cảnh sát chuyên trấn áp tội phạm, Robot nội trợ, Robot có cảm xúc, Robot cảm nhận bằng âm thanh, Robot mô phỏng các hoạt động của con người… Tuy Robot được ứng dụng vào rất nhiều lĩnh vực khác nhau nhưng hiện tại, việc chế tạo Robot vẫn còn gặp rất nhiều khó khăn về kỹ thuật cũng như công nghệ. Thực tế đó đã làm nảy sinh ý tưởng: có thể mô phỏng hoạt động của một Robot trong thế giới thực bằng máy tính được không? Câu trả lời là có và đã có nhiều công ty lớn làm theo cách này. Đây là một hướng phát triển rất quan trọng trong việc chế tạo Robot vì nó giúp cho việc thiết kế cũng như thử nghiệm Robot không còn khó khăn và tốn kém như trước. Tuy nhiên, việc thể hiện toàn bộ hoạt động của một Robot từ thế giới thực lên máy tính là một bài toán khá rộng lớn nên ở đây, trong giới hạn của đề tài này, tôi chỉ tập trung tìm hiểu bài toán “Xây dựng mô hình mô phỏng một đối tượng – tạm gọi là Robot – có khả năng nhận thức môi trường chung quanh để tìm kiếm mục tiêu”. Phần quan trọng của bài toán này là mô phỏng sự nhận thức của Robot, một bài toán tuy nhỏ nhưng không thể thiếu đối với hầu hết các Robot. Mục tiêu của bài toán là mô phỏng cách một Robot tự phân tích môi trường chung quanh để đi tìm vật thể. Giống như con người, đầu tiên Robot phải tìm nó bằng cách đi tìm khắp mọi nơi nhưng khi đã gặp thì Robot sẽ nhớ vị trí đó để định vị cho lần tìm kiếm sau. Và trong quá trình tìm kiếm, Robot phải tìm cách tránh né chướng ngại vật, phải đánh dấu đường đi đã qua, phải tự đưa ra những quyết định khi đã có thêm thông tin… Với bài toán này, các nội dung chính cần đạt được là: Khả năng nhận thức môi trường xung quanh của Robot: Robot sau khi “nhìn” sẽ phân biệt được chướng ngại vật, đường đi hay vật cần tìm trong khung nhìn. Khả năng đưa ra hành vi thích hợp của Robot: sau khi nhận thức được môi trường chung quanh, Robot sẽ đi tìm mục tiêu theo hướng tốt nhất trong các hướng có thể đi được, kết hợp chuyển hướng quan sát nếu gặp phải chướng ngại vật. Khả năng học của Robot: Robot có thể học bằng cách nhớ lại vị trí của vật cần tìm để định vị cho lần tìm kiếm sau. 2. Đặc trưng của bài toán: Do đây là một bài toán tìm kiếm nên nó có một số đặc trưng sau: Thông tin về đối tượng cần tìm có thể chưa chính xác hoặc bị thay đổi (Heuristic chưa có hoặc bị thay đổi) Đối tượng cần tìm có thể ở những nơi mà Robot không bao giờ tìm thấy được vì đối tượng bị che khuất phía sau vật cản. Kết quả là không bao giờ tìm thấy trong trường hợp môi trường cần tìm kiếm rộng lớn (có khả năng thất bại) Có thể có những đường không đi tiếp được mà thoạt đầu Robot chưa biết (có khả năng quay lui) Có thể có những ngã đường buộc Robot phải chọn một trong số các hướng có thể đi được. Trong thực tế, hướng “gần” đối tượng cần tìm lại là hướng xa nhất do cuối cùng phải đi đường vòng (khả năng mạo hiểm trong việc rẽ nhánh) Robot có thể được đặt ở những nơi mà tất cả các hướng Robot đều không thể đi tiếp. Kết quả là Robot sẽ quay lui về tới vị trí xuất phát và ngưng quá trình tìm kiếm (khả năng kết thúc sớm) Đối tượng cần tìm có thể nằm ở những nơi Robot chỉ nhìn thấy nhưng không thể đi đến được (khả năng Robot đi vòng quanh đối tượng càng lúc càng xa) Có thể có những lối đi quá hẹp để Robot có thể đi qua được (coi như đường đang đi là đường không đi tiếp được) Robot nên đi những nơi mà nó chưa đi qua. Do đó có thể có khả năng đối tượng cần tìm nằm ở bên kia đường đã đi rồi. Kết quả là Robot sẽ phải quay lui hoặc đi vòng. CHƯƠNG II : KIẾN THỨC LIÊN QUAN & Do đề tài mô phỏng khả năng nhận thức của Robot nên một số kiến thức sau đây được sử dụng: Đồ hoạ máy tính: để thể hiện giao diện và giải quyết một số vấn đề kỹ thuật như: tạo khung nhìn, thu thập thông tin về những đối tượng trong khung nhìn … Trí tuệ nhân tạo: hỗ trợ khả năng nhận thức và đưa ra quyết định nhằm phục vụ cho việc tìm kiếm. Lập trình hướng đối tượng: vì tính chất của đề tài là mô phỏng thế giới thực nên lập trình hướng đối tượng là một cách tiếp cận hiệu quả nhất. UML (Unified Modeling Languge): được sử dụng để lên mô hình cho dự án . I. ĐỒ HỌA MÁY TÍNH: Đồ hoạ máy tính là một trong những lĩnh vực phát triển nhanh nhất và lý thú nhất của ngành tin học. Ngay từ khi xuất hiện, đồ họa máy tính đã cuốn hút rất nhiều người thuộc nhiều lĩnh vực khác nhau. Và nhờ có công nghệ đồ họa mà con người có thể làm quen dễ dàng với máy tính. Do đó, để thể hiện giao diện cũng như giải quyết một số vấn đề kỹ thuật, đề tài này cũng dùng đến một số kỹ thuật sau: Tiếp cận Camera tổng hợp: sử dụng cách tiếp cận này để tạo ra khung nhìn cho Robot. Các giải thuật xén: để lấy các đối tượng trong khung nhìn của Robot nhằm mô phỏng việc Robot chỉ có thể thấy những gì nằm trong khung nhìn của nó mà thôi. 1. Khái niệm : Đồ họa là quá trình đưa ra một bức ảnh dựa vào một số mô tả. Để làm được điều này chúng ta phải thực hiện đồng thời 2 việc: thứ nhất là đưa ra một tiếp cận khả dĩ mô tả được các đối tượng từ đơn giản đến phức tạp, thứ hai là xây dựng một tập đầy đủ các công cụ vẽ ảnh cho phép đưa ra những bức ảnh từ những nét phác thảo thô sơ cho đến những hình ảnh sống động đầy hiện thực. Nói cách khác, đồ họa máy tính là tất cả những gì liên quan đến việc sử dụng máy tính để phát sinh ra hình ảnh. Các vấn đề liên quan đến công việc này bao gồm: tạo, lưu trữ, thao tác trên các mô hình hình học của đối tượng và các ảnh. 2. Các ứng dụng tiêu biểu của kỹ thuật đồ họa: 2.1 Xây dựng giao diện người dùng (User Interface) Giao diện đồ họa đang được đa số người dùng ưa thích nhờ tính thân thiện, dễ sử dụng của nó. Ưu điểm của nó so với ứng dụng console có thể được tóm tắt như sau: Người dùng có thể nắm bắt dễ dàng nếu các icon được thiết kế tốt để gợi nhớ về chức năng của nó. Có khả năng mở rộng giao diện, nhiều cửa sổ. 2.2 Lĩnh vực giải trí, nghệ thuật và mô phỏng : Các phần mềm đồ họa có thể cho phép các họa sĩ tạo ra các hình ảnh ngay trên màn hình máy tính. Người họa sĩ được máy tính cung cấp các công cụ làm việc rất đầy đủ như: khung vẽ, bảng pha màu, các thao tác cắt, dán, tẩy, xóa, phóng to, thu nhỏ và rất nhiều công cụ toán học khác nhau mà họa sĩ trên khung vải không sao có được. Các phần mềm khác để xây dựng các hình ảnh động và các kỹ xảo hoạt hình cũng có đầy đủ chức năng như vậy. Hiện tại công nghệ VRML đang phát triển rất nhanh cho phép tạo ra các thế giới thực tại ảo trên máy tính cũng như cho phép xây dựng những ứng dụng trong giải trí, trò chơi, thương mại. 3. Giải thuật xén- Clipping: Xén là tiến trình xác định các điểm của một đối tượng nằm trong hay ngoài cửa sổ hiển thị. Đặc trưng của bài toán xén hình là loại bỏ các phần hình ảnh nằm ngoài một vùng cho trước. Hiện nay có 2 hướng tiếp cận xén thông dụng là cắt và tô. Phương pháp cắt được dùng trong trường hợp hình nhỏ hơn vùng cần xén. Trong khi đó, phương pháp tô được dùng trong trường hợp hình lớn hơn vùng cần xén. Vì tính chất của đề tài này là hình ảnh rất lớn so với vùng cần xén (chứa luôn vùng cần xén) nên ở đây tôi chọn phương pháp tô mà không chọn phương pháp cắt. Dựa trên phương pháp tô này, thay vì tô màu ở những vị trí cần tô ta lấy thông tin về đối tượng tại đó. Có hai cách tiếp cận chính để tô màu một vùng tô là: tô theo dòng quét (scan-line fill) và tô theo đường biên (boundary fill). Phương pháp tô màu theo dòng quét thường được dùng để tô màu các đa giác và một số đường cong đơn giản. Còn phương pháp tô màu theo đường biên thường được dùng cho các vùng tô có đường biên phức tạp hơn. Vì khung nhìn của Robot chỉ là một đa giác đơn giản nên phương pháp tô màu theo dòng quét được sử dụng thay vì phương pháp tô màu theo đường biên. Giải thuật tô màu đa giác theo dòng quét – Scanline: Giải thuật dựa trên ý tưởng sử dụng một đường quét trên trục y của màn hình đi từ ymax đến ymin của vùng cần được tô màu. Với mỗi giá trị y = yi đường thẳng quét cắt các đường biên của vùng cần tô tạo ra đoạn thẳng y = yi với giới hạn x Ỵ [xmin - xmax]. Trên đoạn thẳng đó chúng ta tô màu các điểm tương ứng đi từ xmin --> xmax . Các điểm cần tô màu sẽ là (xi, yi) thuộc đoạn thẳng y = yi nói trên. Phép tô màu hình chữ nhật với giải thuật Scanline là phép tô màu đơn giản nhất bởi với mọi đường quét y = yi ta đều thu được hai giá trị xmin và xmax như nhau. Phép tô màu cho một đa giác bất kỳ sẽ phức tạp hơn rất nhiều so với hình chữ nhật. Độ phức tạp ở đây sẽ xảy ra từ việc xác định giải thuật cho việc tính giao điểm của đường thẳng quét để tìm ra đường biên xấp xỉ khi tô màu đến việc suy diễn đưa ra các phần đoạn thẳng cần tô màu trên đường thẳng quét khi gặp loại hình đa giác lõm hay điểm cắt trùng với đỉnh của đa giác khi mô tả. Phép tô màu một đa giác điển hình (như hình vẽ) sẽ theo những bước sau: Tìm giao điểm của đường thẳng quét với các cạnh của đa giác. Sắp xếp các giao điểm theo thứ tự tăng dần của giá trị biến x. Tô màu từng đoạn thẳng nằm giữa cặp điểm giao của đường thẳng quét và cạnh của đa giác. Trong bước này, ta phải giải quyết một vấn đề nảy sinh khi đường thẳng quét đi qua đỉnh của đa giác. Giả sử rằng tại đỉnh của đa giác, đường thẳng quét sẽ cắt 2 cạnh của đa giác tại hai điểm chồng khít lên nhau. Bài toán sẽ có lời giải trong một số trường hợp khi số điểm cắt là chẵn. Với số điểm cắt lẻ thì chúng ta không thể tìm được các cặp điểm cần tô màu. Để khắc phục nhược điểm trên ta sắp xếp các đỉnh mà dòng quét đi qua. Giải thuật sau đây sẽ cho phép ta quyết định lấy P là một điểm hay hai điểm trùng khớp nhau vào danh sách các điểm cắt. Nếu P là giao điểm của 2 cạnh đa giác có hướng ngược nhau, một cạnh có giá trị y tăng khi x tăng, một cạnh có giá trị y giảm khi x tăng thì dòng quét tạo ra hai điểm giao trên P. Ngược lại, nếu P là đỉnh chung của 2 cạnh đa giác có hướng y cùng nhau, y tăng khi x tăng thì đỉnh P cung cấp 1 điểm giao duy nhất cho danh sách điểm giao. Điều này được minh họa như sau: 4. Camera tổng hợp: Giống như con người, Robot cũng có khả năng nhìn và nhận biết được sự có mặt của các đối tượng trong phạm vi quan sát. Để mô phỏng khả năng này của Robot trên máy tính, tôi sử dụng cách tiếp cận camera tổng hợp với các đặc điểm sau: Là một công cụ hữu hiệu mà gói đồ họa 3D như CORE (Bergeron 1978), GKS3D và PHIGS (Brown 1985) cung cấp nhằm hỗ trợ cho việc lấy ảnh của thế giới thực. Camera tổng hợp có một mặt phẳng quan sát và một con mắt. Mặt phẳng quan sát xác định hệ tọa độ quan sát. Cửa sổ mô tả trong mặt phẳng quan sát. Con mắt, cửa sổ và các mặt phẳng trước, sau xác định khối quan sát. Các cạnh đều bị xén qua 6 mặt của khối quan sát này, phần còn lại được chiếu lên mặt phẳng quan sát, chuyển đến NDC (thiết bị đồ họa chuẩn) và cuối cùng được vẽ lên thiết bị. Nói cách khác, Camera tổng hợp mô tả một camera định vị và định hướng trong không gian, gồm 3 phần chính: Mặt phẳng quan sát (view plane) trong đó có định nghĩa một cửa sổ (window). Hệ quan sát. Và một con mắt. Hình vẽ minh họa một camera như vậy lơ lửng trong hệ tọa độ thực (World Coordinate System). Con mắt nhìn xuyên qua cửa sổ và thấy một phần thế giới thực. Có thể coi camera tổng hợp như là một hệ tọa độ được để tự do di chuyển trong không gian, mang theo mặt phẳng quan sát và con mắt. Các thành phần của camera tổng hợp: Gốc tọa độ của hệ UVN là điểm VRP (View Reference Point) nằm trong mặt phẳng quan sát, được mô tả bằng r = (rx, ry, rz). Pháp tuyến của mặt phẳng quan sát xác định trục N của hệ UVN, là vector VPN (View Plane Normal). Hệ UVN được chọn là hệ tọa độ nghịch, các vector chỉ hướng tương ứng là u, v, n và ta có u = n x v. Tính mềm dẻo của mô hình Camera tổng hợp: Các thành phần của Camera cho phép điều khiển sự quan sát phù hợp với cách di chuyển đầu của chúng ta. VRP (vector r) xác định vị trí của người quan sát, di chuyển VRP giống như di chuyển đầu mà không thay đổi hướng nhìn. VPN (vector n) xác định hướng nhìn. Thay đổi VPN giống như động tác quay đầu. Thay đổi “hướng lên” (thay đổi vector v) giống như nghiêng đầu mà vẫn giữ mắt cố định trên đối tượng. II. TRÍ TUỆ NHÂN TẠO Trong cuộc sống ngày nay, máy tính là một trợ thủ đắc lực và không thể thiếu của con người trong việc xử lý thông tin. Không những thế, máy tính còn có khả năng giải quyết các nhiệm vụ ở mức độ trí tuệ ngày càng cao. Theo một nghĩa nào đó, máy tính đã được trang bị trí tuệ nhân tạo. Mục tiêu của trí tuệ nhân tạo là nghiên cứu các kỹ thuật làm cho máy tính có thể “suy nghĩ một cách thông minh”. Theo một nghĩa hẹp, trí tuệ nhân tạo nghĩa là mô phỏng quá trình suy nghĩ của con người khi đưa ra những quyết định, những lời giải bằng cách tìm kiếm thông tin trong không gian bài toán. Từ đó thiết kế các chương trình cho máy tính để giải quyết bài toán trong quá trình tìm kiếm. Trên cơ sở đó, ta ứng dụng kỹ thuật tìm kiếm của trí tuệ nhân tạo vào đề tài nhằm giải quyết bài toán tìm kiếm của Robot. 1. Khái niệm: Trong thực tế, nhiều dạng hoạt động của con người từ những tính toán trong các nghiên cứu khoa học kỹ thuật, các bài toán xử lý dữ liệu cỡ lớn trong quản lý kinh tế xã hội đến những hoạt động ít nhiều mang tính giản đơn như giải đáp câu đố, chơi cờ, sửa chữa máy móc … đều đòi hỏi sự tham gia của trí tuệ. Trí tuệ nhân tạo là một ngành khoa học chuyên nghiên cứu và tạo ra các chương trình thực hiện các công việc như con người hoặc mô phỏng hoạt động của não người. Ngoài ra, trí tuệ nhân tạo còn làm cho máy tính có khả năng suy nghĩ cũng như có thể mô phỏng quá trình học của con người. Có thể nhận thấy rằng bộ não của con người có thể tích hợp những tri thức mới mà không cần phải thay đổi cách thức làm việc, không cần phải thay đổi cách suy diễn trong não bộ hoặc loại bỏ đi những sự kiện đã được lưu trước đó. Trên cơ sở đó các chuyên gia trí tuệ nhân tạo cố gắng làm cho các chương trình trí tuệ nhân tạo hoạt động tương tự như thế. 2. Các lĩnh vực nghiên cứu và ứng dụng cơ bản của Trí Tuệ Nhân Tạo: Sự phát triển mạnh mẽ của trí tuệ nhân tạo và tin học trong những thập niên gần đây đã tạo ra ngày càng nhiều sản phẩm thông minh phục vụ trong đời sống hằng ngày, trong công nghiệp cũng như trong các ngành khoa học. Từ đó có thể phân chia các lĩnh vực nghiên cứu và ứng dụng quan trọng của trí tuệ nhân tạo theo 4 hướng cơ bản sau : Mô hình hoá trên máy tính những chức năng khác nhau trong quá trình sáng tạo như : các trò chơi, chứng minh tự động các định lý, tổng hợp tự động các chương trình … Nâng cao khả năng trí tuệ “bên ngoài” của máy tính gắn liền với các giao tiếp, hội thoại bằng cách sử dụng các kỹ thuật suy diễn và tìm kiếm. Nâng cao khả năng trí tuệ “bên trong” của máy tính trên cơ sở chế tạo các máy tính thế hệ mới với kiến trúc vật lý mới dựa trên các nguyên lý của trí tuệ nhân tạo. Chế tạo các Robot thông minh có khả năng thực hiện những thao tác phức tạp, có thể ”suy nghĩ” và “hành động” để đạt đến mục đích đã đặt ra. 3. Các phương pháp và kỹ thuật Trí Tuệ Nhân Tạo Các bài toán trí tuệ nhân tạo trải rộng trong nhiều lĩnh vực khác nhau nên việc giải quyết chúng đòi hỏi phải đáp ứng những yêu cầu về phương diện kỹ thuật tin học và cả về thiết bị tương ứng. Các phương pháp và kỹ thuật trí tuệ nhân tạo cơ bản bao gồm: Các phương pháp biểu diễn tri thức và công nghệ xử lý tri thức. Các phương pháp giải quyết vấn đề. Các phương pháp Heuristic. Các phương pháp học. Các ngôn ngữ trí tuệ nhân tạo. Xử lý danh sách, kỹ thuật đệ quy, kỹ thuật quay lui … là những kỹ thuật cơ bản của tin học truyền thống có liên quan trực tiếp đến trí tuệ nhân tạo. Vì đề tài sử dụng các phương pháp tìm kiếm Heuristic và phương pháp học nên ở đây chỉ đề cập đến hai phương pháp này. Còn những phương pháp khác nếu có nhu cầu tìm hiểu thêm, xin xem thêm ở tài liệu tham khảo. 4. Các Giải Thuật Tìm Kiếm Heuristic Lập trình Heuristic là một hướng tiếp cận quan trọng trong việc xây dựng các hệ thống trí tuệ nhân tạo. Lý thuyết tìm kiếm Heuristic bao gồm các phương pháp và các kỹ thuật tìm kiếm, sử dụng các tri thức đặc biệt nảy sinh từ bản thân bài toán cần giải để rút ngắn quá trình giải, nhanh chóng đi đến kết quả mong muốn. Kỹ thuật cơ bản dựa trên các tri thức Heuristic hay được sử dụng trong thực tiễn là các hàm đánh giá. 4.1 Giải thuật leo đồi Giải thuật leo đồi là một giải thuật tìm kiếm dựa trên hàm đánh giá theo chiều sâu nghĩa là chỉ tập trung tìm kiếm theo một hướng. Những nét chính của thuật giải Thuật giải sử dụng 2 danh sách: Danh sách mở Open, chứa các đỉnh sẽ được xem xét ở các bước kế tiếp. Danh sách đóng Close, chứa các đỉnh đã được xem xét. Các đối tượng chính trong thuật giải: Đỉnh bắt đầu s Đỉnh kết thúc g Đỉnh đang xét n Danh sách B(n) chứa các đỉnh đi được từ đỉnh n. Thuật giả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 sách mở Open được sử dụng trong trường hợp này là Stack. 4.2 Giải thuật A*: Giải thuật A* là một giải thuật tìm kiếm dựa trên hàm đánh giá theo chiều rộng với các thông tin Heuristic cho phép sắp xếp lại các đỉnh. Những nét chính của thuật giải: Thuật giải cũng sử dụng 2 danh sách: Danh sách mở Open, chứa các đỉnh sẽ được xem xét ở các bước kế tiếp. Danh sách đóng Close, chứa các đỉnh đã được xem xét. Các đối tượng chính trong thuật giải: Đỉnh bắt đầu s Đỉnh kết thúc g Đỉnh đang xét n Danh sách B(n) chứa các đỉnh đi được từ đỉnh n. Thuật giả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 <đặt lại tham chiếu cho m’) 2.4.3 .2 if (m’ Ỵ Close ) < chuyển m’ qua Open ) 3. return false Danh sách mở Open được sử dụng trong trường hợp này là Queue. III. LẬP TRÌNH HƯỚNG ĐỐI TƯỢNG VỚI VISUAL C++ Thực tế, mọi thứ trong thế giới thực đều có thể được xem như đối tượng. Do đó, để mô phỏng thế giới thực thì không có hướng tiếp cận nào tốt hơn hướng đối tượng. Trong số các ngôn ngữ hỗ trợ hướng đối tượng thì C++ được xem là ngôn ngữ lập trình thông dụng nhất. Hiện nay, trên thị trường có nhiều công cụ hỗ trợ lập trình trên C++ như Borland C++, Watson C++, Visual C++… trong đó Visual C++ của hãng Microsoft được ưa chuộng nhất vì tính thân thiện, dễ sử dụng và hỗ trợ triển khai ứng dụng nhanh. Vì thế, tôi chọn Visual C++ làm công cụ phát triển ứng dụng của mình trong đề tài này. 1. Khái niệm về lập trình hướng đối tượng: 1.1 Tổng quan: Lập trình hướng đối tượng (Object-Oriented Programming – gọi tắt là OOP), hay chi tiết hơn là lập trình định hướng đối tượng, là một phương pháp lập trình lấy đối tượng (object) làm nền tảng để xây dựng thuật giải, xây dựng chương trình. Lập trình hướng đối tượng đặt trọng tâm vào đối tượng - yếu tố quan trọng trong quá trình phát triển chương trình- và không cho phép dữ liệu biến động tự do trong hệ thống. Dữ liệu được gắn chặt với các hàm thành các vùng riêng mà chỉ có các hàm đó tác động lên và cấm các hàm bên ngoài truy cập tới một cách tuỳ tiện. Lập trình hướng đối tượng cho phép chúng ta phân tích bài toán thành các thực thể được gọi là các đối tượng và sau đó xây dựng các dữ liệu cùng các hàm xung quanh các đối tượng đó. Các đối tượng có thể tác động, trao đổi thông tin với nhau thông qua cơ chế truyền nhận thông điệp (message). Việc tổ chức một chương trình hướng đối tượng có thể được mô tả như sau: Đối tượng A Dữ liệu Đối tượng B Dữ liệu Đối tượng C Dữ liệu message Lập trình hướng đối tượng có các đặc tính chủ yếu sau: Tập trung vào dữ liệu thay cho các hàm. Chương trình được chia thành các đối tượng. Cấu trúc dữ liệu được thiết kế sao cho đặc tả được đối tượng. Các hàm thao tác trên các vùng dữ liệu của đối tượng được gắn với cấu trúc dữ liệu đó. Dữ liệu được đóng gói lại, được che giấu và không cho phép các hàm ngoại lai truy cập tự do. Các đối tượng tác động và trao đổi thông tin với nhau qua các hàm Có thể dễ dàng bổ sung dữ liệu và các hàm mới vào đối tượng nào đó khi cần thiết. Chương trình được thiết kế theo cách tiếp cận từ dưới lên (bottom-up). Sau đây là một số khái niệm được sử dụng trong lập trình hướng đối tượng. 1.2 Một số khái niệm: Đối tượng (object) Đối tượng là sự kết hợp giữa dữ liệu và phương thức thao tác trên dữ liệu đó. Có thể đưa ra công thức phản ánh bản chất kỹ thuật của lập trình hướng đối tượng như sau: Đối tượng = dữ liệu + phương thức Lớp (class) Lớp là một khái niệm mới trong lập trình hướng đối tượng so với các kỹ thuật lập trình khác. Đó là một tập các đối tượng có cấu trúc dữ liệu và các phương thức giống nhau (hay nói cách khác là một tập các đối tượng cùng loại). Như vậy khi có một lớp thì chúng ta sẽ biết được một mô tả cấu trúc dữ liệu và phương thức của các đối tượng thuộc lớp đó. Mỗi đối tượng sẽ là một thể hiện cụ thể (instance) của lớp đó. Trong lập trình, chúng ta có thể coi một lớp như là một kiểu còn các đối tượng sẽ là các biến có kiểu của lớp. Nguyên tắc đóng gói dữ liệu Trong lập trình hướng đối tượng ta đã thấy các hàm hay thủ tục được sử dụng mà không cần biết nội dung cụ thể của nó. Người sử dụng chỉ cần biết chức năng của hàm cũng như các tham số cần truyền vào để gọi hàm thực thi mà không cần quan tâm đến những lệnh cụ thể bên trong nó. Người ta gọi đó là sự đóng gói về chức năng. Trong lập trình hướng đối tượng, không những chức năng được đóng gói mà cả dữ liệu cũng như vậy. Với mỗi đối tượng, người ta không thể truy cập trực tiếp vào các thành phần dữ liệu của nó mà phải thông qua các thành phần chức năng (các phương thức) để làm việc đó. Chúng ta sẽ thấy sự đóng gói thực sự về dữ liệu chỉ có trong một ngôn ngữ lập trình hướng đối tượng “thuần khiết” (pure) theo nghĩa các ngôn ngữ được thiết kế ngay từ đầu chỉ cho lập trình hướng đối tượng. Còn đối với các ngôn ngữ “lai” (hybrid) được xây dựng trên các ngôn ngữ khác (ban đầu chưa phải là hướng đối tượng) như C++ vẫn có những ngoại lệ nhất định vi phạm nguyên tắc đóng gói dữ liệu. Tính thừa kế (inheritance) Một khái niệm quan trọng của lập trình hướng đối tượng là sự thừa kế. Sự thừa kế cho phép chúng ta định nghĩa một lớp mới trên cơ sở các lớp đã tồn tại có bổ sung những phương thức hay các thành phần dữ liệu mới. Khả năng kế thừa cho phép chúng ta sử dụng lại một cách dễ dàng các module chương trình mà không cần thay đổi các module đó. Đây là một điểm mạnh của lập trình hướng đối tượng so với lập trình cấu trúc. Tính đa hình (polymorphime) Tính đa hình xuất hiện khi có khái niệm kế thừa. Giả sử chúng ta có một kế thừa lớp hình tứ giác và tam giác từ lớp hình đa giác (hình tam giác và tứ giác có đầy đủ các thuộc tính và tính chất của một hình đa giác). Lúc này một đối tượng thuộc lớp hình tam giác hay tứ giác đều có thể hiểu rằng nó là một hình đa giác. Mặt khác với mỗi đa giác ta có thể tính diện tích của nó. Như vậy làm thế nào mà một đa giác có thể sử dụng đúng công thức để tính diện tích phù hợp với nó là hình tam giác hay tứ giác. Ta gọi đó là tính đa hình. 1.3 Các ưu điểm của lập trình hướng đối tượng: Lập trình hướng đối tượng đem lại một số lợi thế cho người thiết kế lẫn người lập trình. Cách tiếp cận hướng đối tượng giải quyết được nhiều vấn đề tồn tại trong quá trình phát triển phần mềm và tạo ra được những phần mềm có độ phức tạp và chất lượng cao. Phương pháp này mở ra một triển vọng to lớn cho người lập trình. Những ưu điểm chính của lập trình hướng đối tượng là: Thông qua nguyên lý kế thừa, chúng ta có thể loại bỏ được những chương trình lặp lại trong quá trình mô tả các lớp và có thể mở rộng khả năng sử dụng của các lớp đã xây dựng mà không cần phải viết lại. Chương trình được xây dựng từ những đơn thể (đối tượng) trao đổi với nhau nên việc thiết kế và lập trình sẽ được thực hiện theo quy trình nhất định chứ không phải dựa vào kinh nghiệm và kỹ thuật như trước nữa. Điều này đảm bảo rút ngắn được thời gian xây dựng hệ thống và tăng năng suất lao động. Nguyên lý đóng gói hay che giấu thông tin giúp lập trình viên tạo ra được những chương trình an toàn không bị thay đổi bởi những đoạn chương trình khác. Có thể xây dựng được ánh xạ các đối tượng của bài toán vào đối tượng chương trình. Cách tiếp cận thiết kế đặt trọng tâm vào dữ liệu, giúp chúng ta xây dựng được mô hình chi tiết và dễ dàng cài đặt hơn. Các hệ thống hướng đối tượng dễ mở rộng, nâng cấp thành những hệ lớn hơn. Kỹ thuật truyền thông điệp trong việc trao đổi thông tin giữa các đối tượng làm cho việc mô tả giao diện với các hệ thống bên ngoài trở nên đơn giản hơn. Có thể quản lý được độ phức tạp của những sản phẩm phần mềm. Với nhiều đặc tính phong phú của lập trình hướng đối tượng nói riêng, của phương pháp phân tích thiết kế và phát triển hướng đối tượng nói chung, chúng ta hy vọng công nghiệp phần mềm sẽ có những cải tiến vượt bậc không những về chất lượng mà còn gia tăng nhanh về số lượng trong tương lai. 2. Ngôn ngữ lập trình Visual C++ trên môi trường Windows 2.1 Tổng quan: Như chúng ta đã biết, các chương trình ứng dụng ngày nay thường là phức tạp và quy mô hơn so với trước đây. Hơn nữa, bên cạnh quy mô lớn và phức tạp thì giao diện đồ họa gần như không thể thiếu trong những chương trình ứng dụng này. Tuy nhiên, cho dù các chương trình ứng dụng ngày càng đòi hỏi tính quy mô, phức tạp hơn thì người lập trình vẫn có khả năng giảm thiểu các công việc của mình nếu họ chọn được một công cụ lập trình hợp lý. Visual C++ là một trong những công cụ nói trên. Với code-generating wizards, Visual C++ có thể tạo ra khung sườn cho các chương trình ứng dụng thực thi trong môi trường Windows trong vòng vài giây. Các lớp thư viện đi kèm với Visual C++ như là Microsoft Foundation Classes (MFC) đã trở thành một trong các tiêu chuẩn để phát triển các phần mềm dưới môi trường Windows cho các trình biên dịch C khác nhau. Bên cạnh đó, các công cụ soạn thảo khả kiến cũng tạo ra cho chúng ta các công cụ hữu hiệu để có thể tạo các menu và các hộp hội thoại. Nói tóm lại, việc nghiên cứu Visual C++ là một việc làm cần thiết cho các nhà lập trình ứng dụng khi viết các chương trình thực thi trong môi trường Windows và giao diện đồ họa. Để cung cấp cho lập trình viên một môi trường làm việc hiệu quả, Microsoft Developer Studio đã kết hợp các giai đoạn của việc lập trình như soạn thảo, biên dịch và kiểm tra lỗi lại thành một giao diện duy nhất, điều đó có nghĩa chúng ta có thể cài đặt hay xoá bỏ các Breakpoint phục vụ cho việc Debug chương trình trong cùng một giao diện với việc soạn thảo phần Source code. Hơn thế nữa, khi chúng ta tiến hành xây dựng một đề án, môi trường phát triển tích hợp (IDE - Integrated Development Environment) có thể phát hiện các lỗi và cho phép chúng ta tiếp cận ngay đến vị trí lỗi đó một cách nhanh chóng cho dù tập tin chứa các lỗi này chưa được mở. Với Microsoft Visual C++, chương trình ứng dụng thường được xây dựng trên cơ sở các lớp (classes). Có rất nhiều lớp khác nhau đã được xây dựng sẵn thành thư viện để phục vụ cho người lập trình. Chẳng hạn như lớp CDC là lớp phục vụ rất đắc lực cho việc vẽ hình trong các ứng dụng viết bằng Visual C++. Lớp CDC Một cách chuyên dụng, lớp CDC được thiết kế cho mục đích chính là vẽ hình để tạo những hình ảnh thông báo hay để thực thi hàm OnDraw() khi chúng ta cần làm việc trong các cửa sổ. Trong thực tế thì lớp CDC được thiết kế bao gồm hai nhóm Device Context: một dùng cho việc quản lý các quá trình vẽ và một dùng cho việc quản lý các quá trình hỏi đáp – truy vấn (query). Việc quản lý quá trình vẽ trên các DC được thực thi bởi m_hDC và việc quản lý các quá trình chất vấn là do m_hAttribDC. Khi chúng ta can thiệp vào CDC dù với một công việc sơ đẳng nhất thì đáp ứng tương tự sẽ xảy ra cho DC tương ứng. Do đó chúng ta có thể thực hiện các công việc một cách đơn giản là sử dụng các hàm thành phần của CDC. Đồng thời Windows cũng giới thiệu một thư viện GDI (Graphic Device Interface). Thư viện này giúp cho chương trình viết ra có thể tiếp cận driver Video và Printer của hệ thống một cách dễ dàng. Chương trình này có thể gọi các hàm chức năng của GDI, tham khảo cấu trúc của các dữ liệu bằng cách gọi Device Context. Windows sẽ ánh xạ cấu trúc Device Context thành Physical Device và đưa ra Input/Output tương ứng. Microsoft Developer Studio và tiến trình xây dựng: Visual C++ là một thành phần của Microsoft Developer Studio là IDE (Integrated Development Environtment). IDE có nguồn gốc từ Visual Workbench dựa trên Quick C cho Window. Microsoft Developer Studio cung cấp khả năng : Help Online làm việc như một Web Browser. AppWizard Có thể xem Project ở nhiều khía cạnh (editor, workspace) ClassWizard Xây dựng giao diện gồm trình đơn và các khung đối thoại Compiling, Linking Debugging Tiến trình xây dựng một ứng dụng của Visual C++ : Ở đây, trong phạm vi đề tài này, chúng ta chỉ nghiên cứu lập trình C++ với sự hỗ trợ của thư viện MFC (Microsoft Foundation Class). Thư viện này là một công cụ quan trọng để xây dựng nhanh các chương trình ứng dụng Windows sử dụng Visual C++. Nó cũng làm cho việc lập trình dễ dàng hơn bằng cách cung cấp những lớp, những đối tượng với các hành vi (Methods) và các thuộc tính (Properties). 2.2 Thư viện MFC: Thư viện MFC hỗ trợ 2 loại ứng dụng: SDI (Single Document Interface) và MDI (Multi Document Interface). Với loại SDI thì ta chỉ có một cửa sổ Windows. Dựa trên dạng tập tin (file Document) thì chỉ có một tập tin được load lên. MDI thì có nhiều cửa sổ con, mỗi cửa sổ con này hướng tới một tập tin. 2.2 .1 Window Messages: Mọi hoạt động trên FrameWork đều thông qua thông điệp, tương ứng với mã nhận diện ID ta sẽ có các lệnh tương ứng với các thông điệp Window. Ví dụ như người sử dụng di chuyển con chuột thì cửa sổ này sẽ nhận được thông điệp WM_MOUSEMOVE. Chương trình cần phải đáp ứng bằng một hàm chức năng tự tạo. Macro afx_msg là nơi khai báo hàm thành viên đáp ứng thông điệp. Để tạo hàm xử lý thông điệp ta sử dụng ClassWizard chọn lớp cơ sở để chứa nó, sau đó chọn Window Message tương ứng sau khi đã có sự đồng ý thì nó được ánh xạ vào trong chương trình. Khi đó ta có thể phát triển hàm xử lý tương ứng với thông điệp đó. Các thông điệp lệnh mang những hàm giải quyết mặc định trong MFC như với MenuFile: New, Open, Close, Save...Edit: Clear, ClearAll, Cut...View: Toolbar, Statusbar... Thông điệp Window (bắt đầu bằng WM_) giải quyết chận hứng thông điệp. Ngoài các thông điệp mặc định, ta có thể định nghĩa chúng bằng cách vào WM_USER. 2.2 .3 Hộp thoại ở chế độ Modal và Modalless: Dialog giống như một cửa sổ và nó cũng có thể chứa các control khác. Ta có thể gán trên nó Editboxes, Button, Listboxes, Comboboxes, Static Text, TreeView, progress indicator... hay sắp xếp cũng như tạo Tab ưu tiên cho từng mục chọn (Tab order). Visual C++ có hai loại dialog là Modal và Modaless như sau: Modal Dialog: loại này thường được dùng khi mở Dialog và đợi user đóng Dialog lại nếu muốn qua cửa sổ khác. Khi xây dựng xong cần phải có một Method gọi nó. Gọi bằng hàm thành viên của CDialog::DoModal() đồng thời phải khai báo #include “tên file header định nghĩa Dialog” vào nơi gọi nó. Modalless Dialog: Dialog ở dạng này cho phép không đóng Dialog khi không làm việc trên nó nữa. IV. GIỚI THIỆU VỀ UML Trong thực tế, để làm một dự án nào đó người ta thường phải xây dựng mô hình trước, sau đó mới tiến hành làm theo mô hình định sẵn. Nếu không có mô hình, những dự án đó thường dẫn đến những phát sinh ngoài dự kiến làm ảnh hưởng nhiều đến khả năng hoàn thành dự án. Hiện nay, một ngôn ngữ hỗ trợ việc lên mô hình được sử dụng nhiều nhất là UML. Do đó, tôi cũng sử dụng ngôn ngữ này để lên mô hình cho dự án của mình. 1. Tổng quan: UML (Unified Modeling Languge) là một ngôn ngữ mô hình hóa được xây dựng lần đầu tiên bởi Booch, Rumbaughvà Jacobson. Nó mô hình hệ thống thế giới thực thành một model. Một model bao gồm một số View, mỗi View sẽ diễn tả một mặt, một khía cạnh của hệ thống. Nội dung trong một View được mô tả bởi nhiều diagram, mỗi diagram bao gồm các Model Element như: class, object, note, component, relationship. Mỗi element có một ngữ nghĩa và một ký hiệu đồ họa biểu diễn nó. Các diagram của UML gồm: class diagram, object diagram, activity diagram và deployment diagram. UML còn có một số kỹ thuật chung để thêm vào các thông tin không thể vẽ được trong mô hình. Các kỹ thuật này gồm adorment đặt cạnh element, note để biểu diễn thông tin bất kỳ và các thuộc tính đặc biệt. Ngoài ra còn các kỹ thuật mở rộng gồm tagged, constraint và stereotype. UML không chỉ là sự chuẩn hóa và tìm ra ký hiệu thống nhất mà nó còn bao gồm những khái niệm mới như: cách mô tả và sử dụng pattern (mẫu thiết kế|) trong ngôn ngữ mô hình hóa, cách sử dụng khái niệm stereotype để mở rộng và chuyển đổi mô hình… Vì vậy, việc tìm hiểu UML không chỉ là hiểu về các biểu tượng và ý nghĩa của chúng mà còn là hiểu về mô hình hóa hướng đối tượng một cách thật sự. 2. Công dụng của UML: UML có thể mô hình hóa nhiều loại hệ thống khác nhau. Nó còn có thể được dùng trong các phase khác nhau trong quá trình phát triển hệ thống. Mục tiêu của UML là có thể mô tả được bất kỳ kiểu hệ thống nào theo hình thức các diagram hướng đối tượng như: hệ thống thông tin, hệ thống kỹ thuật, hệ thống phân bố… Hầu hết các hệ thống đều không phù hợp hoàn toàn với một trong các loại trên mà chúng có thể thuộc nhiều loại hệ thống cùng lúc. UML có khả năng mô hình hóa tất cả các loại hệ thống này. 3. Khái quát về UML: UML bao gồm các thành phần sau: View: mỗi view chỉ ra một mặt khác nhau của hệ thống được mô hình hóa. Một View có thể bao gồm nhiều diagram. Ngoài ra View còn dùng để liên kết UML với các method/ process của quá trình phần mềm. Diagram: là biểu đồ mô tả nội dung của một View. UML có 9 loại diagram được dùng kết hợp để cung cấp tất cả các View của hệ thống. Model element: là các khái niệm sử dụng trong diagram như class, object, message, relationship (association, dependency, generalization). Một model element có thể được dùng trong nhiều diagram. General mechanism: cung cấp các thông tin đặc biệt hay ngữ nghĩa về một model element. 3.1 View: Một hệ thống không thể được mô tả hết chỉ trong một biểu đồ, nó nên được mô tả riêng cho mỗi khía cạnh khác. Vì vậy, một hệ thống được mô tả bởi một số View, mỗi View phản ánh một mặt của hệ thống. Mỗi View bao gồm nhiều diagram và mỗi diagram cũng có thể thuộc các View khác nhau. Một diagram chứa các ký hiệu đồ họa biểu diễn model element của hệ thống. Các View của UML là: Use-case view: chỉ ra các chức năng của hệ thống đối với các actor bên ngoài. Logical view: chỉ ra các chức năng được thiết kế như thế nào trong hệ thống. Component view: chỉ ra cách tổ chức của code component. Concurrency view: giải quyết vấn đề liên lạc và đồng bộ được biểu diễn trong một hệ thống đồng thời. Deployment view: chỉ việc triển khai hệ thống ra kiến trúc vật lý qua các node (máy tính và thiết bị). 3.2 Diagram: Diagram là biểu đồ chỉ sự sắp xếp các ký hiệu model element nhằm minh họa một phần hoặc một khía cạnh của hệ thống. Một mô hình hệ thống thường có một số loại diagram. Một diagram phải là một phần của một view nào đó và nó cũng có thể thuộc nhiều view khác. UML có 9 loại diagram là : Use-case diagram. Class diagram. Object diagram. State diagram. Sequence diagram. Collaboration diagram. Activity diagram. Component diagram. Deployment diagram. Do đặc thù của đề tài là mô phỏng quá trình nhận thức thế giới xung quanh để tìm kiếm nên một số diagram sau được sử dụng: Class diagram – xây dựng cấu trúc tĩnh của các lớp trong ứng dụng Sequence diagram – lên lược đồ cho quá trình nhận thức Collaboration diagram – lược đồ tương tác của các đối tượng trong ứng dụng Activity diagram – lên lược đồ cho quá trình tìm kiếm Class diagram Class diagram chỉ ra cấu trúc tĩnh của các class trong hệ thống. Các class biểu diễn những gì xử lý trong hệ thống. Các class có thể liên quan với nhau theo một số quan hệ như sau: Associate: nối đến class khác Dependent: một class thuộc/ sử dụng một class khác. Speciallize: một class là một đặc biệt hóa của một class khác. Package: nhóm chung trong một đơn vị. Một hệ thống thường có một số class diagram. Một class cũng có thể tham gia vào nhiều class diagram khác nhau. Collaboration diagram Collaboration diagram biểu diễn sự cộng tác của các object trong hệ thống. Collaboration diagram chỉ sự trao đổi message (được gọi là interaction), nó còn biểu diễn các object và các quan hệ của chúng (được gọi là ngữ cảnh). Ngoài ra , collaboration diagram còn có một chức năng quan trọng là biểu diễn các active object. Các active object có thể cùng thực thi đồng thời do đó chúng được dùng trong việc biểu diễn hệ thống có sự thực thi đồng thời. Sequence diagram. Sequence diagram chỉ sự cộng tác giữa một số object. Nó được sử dụng để xác định trình tự gửi message giữa các object cũng như sự tương tác giữa các object. Sequence diagram gồm các object được xếp theo đường ngang, nó chỉ sự trao đổi message giữa các object theo thời gian (thời gian trôi qua theo hướng đi xuống). Message được biểu diễn như một đường mũi tên nối các object với các đặc tả về thời gian có thể thêm vào bên lề diagram. Do sequence diagram và collaboration diagram khá giống nhau nên việc chọn lựa sử dụng diagram nào được xác định như sau: Nếu muốn nhấn mạnh yếu tố thời gian hay trình tự thực hiện thì ta sử dụng sequence diagram còn nếu muốn nhấn mạnh ngữ cảnh thì ta chọn collaboration diagram. Activity diagram Activity diagram chỉ dòng công việc mà hệ thống cần thực hiện. Activity diagram chú trọng vào kết quả công việc do đó nó được dùng trong việc mô tả use-case hay interaction. Activity diagram bao gồm nhiều action state và mỗi action state chứa đặc tả về một hành động (action) cần được thực hiện. Một action state sẽ thoát khỏi state sau khi nó thực hiện action. Activity diagram còn có thể chỉ ra sự thực thi song song của các action state cũng như đặc tả về thông điệp truyền nhận. 3.3 Model Elements: Các khái niệm sử dụng trong diagram được gọi là model element. Mỗi model element có một view element tương ứng mà nó là ký hiệu đồ họa để biểu diễn element trong diagram. Một model element có thể xuất hiện trong nhiều diagram khác nhau. Một số loại model element là: class, object, package, component, use case, note, interface, state… Relationship (quan hệ) là một loại model element dùng để kết nối giữa các model element nhằm biểu thị mối quan hệ giữa chúng với nhau. Các loại relationship gồm: Association (kết hợp): nối các element và liên kết các instance của chúng. Generalization (tổng quát hóa): còn gọi là quan hệ thừa kế, nghĩa là một element có thể là đặc tả của một element khác. Dependency (phụ thuộc): chỉ ra rằng một element phụ thuộc vào một element khác theo một nghĩa nào đó. Aggregation: một hình thức của association, trong đó một element chứa một element khác. Các model element khác còn có message, action, stereotype… 3.4 Tool: Việc sử dụng một ngôn ngữ mô hình hóa phức tạp như UML đòi hỏi phải có một công cụ hỗ trợ. Công cụ này được gọi là Modeling tool hay Case tool, chẳng hạn như Rational Rose là một Case tool. Một Case tool hiện đại cần cung cấp được các chức năng sau: Vẽ diagram: tool phải hỗ trợ cho việc biểu diễn các diagram trong ngôn ngữ. Nó cũng phải có thể hiểu được mục đích của diagram, biết được các semantic (đặc tả ngữ nghĩa) và rule đơn giản. Như một nơi lưu trữ: tool phải hỗ trợ một nơi lưu trữ chung cho các thông tin trong mô hình. Nếu tên của một class bị thay đổi trong một diagram thì thay đổi này cũng sẽ được phản ánh ở các diagram khác có sử dụng class này. Hỗ trợ navigation: tool có thể dễ dàng dò tìm một element từ diagram này sang diagarm khác. Hỗ trợ multiuser: tool phải hỗ trợ nhiều người sử dụng, cho phép họ cùng làm việc trên một mô hình mà không bị ảnh hưởng lẫn nhau. Phát sinh code: thông tin trong mô hình được chuyển thành khung mã chương trình, làm cơ sở cho giai đoạn cài đặt. Reverse engineer: khả năng đọc code và sinh ra mô hình từ nó. Tích hợp với các tool khác: tool phải có khả năng tích hợp với các tool khác cả về môi trường phát triển như editor, compiler, debugger cũng như các enterprise tool khác như configuration management và version control system. Bao phủ mọi mức trừu tượng của mô hình: tool phải dễ dàng truy tìm từ mức mô tả cao nhất của hệ thống xuống đến mức code. Trao đổi mô hình: một mô hình hay diagram trong mô hình có thể được đem từ một tool này sang tool khác để sử dụng. CHƯƠNG III: HƯỚNG TIẾP CẬN CỦA ĐỀ TÀI Với mục đích là mô phỏng Robot trong thế giới thực nên đề tài sử dụng một số hướng tiếp cận sau: Camera tổng hợp: ứng dụng kỹ thuật Camera tổng hợp để tạo ra khung nhìn cho Robot. Đây là một kỹ thuật rất phức tạp trong đồ họa 3D nên trong giới hạn của đề tài tôi chỉ vận dụng tính chất mềm dẻo của Camera tổng hợp để mô phỏng thế giới 2D như sau: Con mắt đặt ở vị trí đứng của Robot. Cửa sổ quan sát là một đoạn thẳng có thể xoay 8 hướng xung quanh Robot. Tầm nhìn của Robot có thể được thay đổi để thu thập các thông tin mong muốn. Kỹ thuật xén: Trong thực tế, tầm nhìn của Robot có thể được xem như là xa vô hạn. Vì tín hiệu liên tục được truyền đến thiết bị nhận của Robot nên Robot chỉ cần phân tích các tín hiệu đó là đã có thông tin về môi trường. Đứng về mặt lập trình thì khi tầm nhìn của Robot càng xa thì khối lượng công việc phải xử lý càng nhiều. Do mục tiêu của đề tài này là mô phỏng cách nhận thức của Robot để tránh né nên ta không cần cho Robot có tầm nhìn xa. Vì thế kỹ thuật xén được dùng ở đây để giới hạn tầm nhìn của Robot. Kỹ thuật xén được dùng kết hợp với Camera tổng hợp nhằm giải quyết bài toán mô phỏng cách nhìn của Robot như sau: Đầu tiên ta tạo một khung nhìn cho Robot (bằng cách sử dụng tiếp cận Camera tổng hợp) Sau đó ta dùng giải thuật xén để lấy thông tin về các đối tượng nằm trong khung nhìn của Robot. Nguyên tắc xén: Aùp dụng giải thuật tô màu trên không gian tìm kiếm theo khung nhìn của Robot (được tạo ra bởi phương pháp Camera tổng hợp) để lấy thông tin về những đối tượng trong không gian tìm kiếm lọt vào khung nhìn này. Các kỹ thuật tìm kiếm Heristic: Đề tài sử dụng 2 kỹ thuật tìm kiếm của trí tuệ nhân tạo là leo đồi và A*. Tuy có nhiều hướng tiếp cận với phương pháp leo đồi nhưng hiện tại có 2 hướng chính là leo đồi không quay lui và leo đồi có kết hợp quay lui. Trong đề tài này, em sử dụng hướng tiếp cận có quay lui vì nó phù hợp với ý đồ thiết kế của bài toán này. Còn kỹ thuật tìm kiếm A*, do thời gian quá hạn chế nên em không cài đặt kịp. Tuy nhiên đây có thể là một hướng mở rộng, khi có đủ thời gian và điều kiện em sẽ tiếp tục thực hiện nó. CHƯƠNG IV: GIAO DIỆN CỦA ỨNG DỤNG Tăng giảm số lượng vật cản Tăng giảm kích thước không gian tìm kiếm Giao diện của chương trình minh họa lúc khởi động được thiết kế như sau: Stone: đại diện cho vật cản trên đường đi của Robot Robot Treasure: đại diện vật cần tìm Chú thích: Start/Stop search: bắt đầu hoặc ngưng chức năng tìm kiếm Pause/Resume: tạm dừng hoặc tiếp tục quá trình tìm kiếm Close: đóng ứng dụng Show view: bật/ tắt khung nhìn của Robot Show Detail: bật/ tắt bảng thông tin chi tiết về Robot Radius: tăng giảm bán kính khung nhìn Delay time: tăng giảm thời gian delay giữa 2 bước đi của Robot Found Objects: hiển thị số object trong khung nhìn của Robot Giao diện của chương trình minh họa lúc chạy như sau: Đường Robot đã đi qua Khung nhìn của Robot Bảng thông tin chi tiết của Robot PHẦN II : THIẾT KẾ CHƯƠNG TRÌNH 1. Thiết kế mức quan niệm: Ở mức quan niệm ta chỉ quan tâm đến các lớp chính và sự tương tác giữa chúng với nhau. 1.1 Sơ đồ lớp với các lớp chính: Mô tả: Sơ đồ có 5 lớp chính với ý nghĩa như sau: Lớp Object2D là mẫu của các đối tượng 2D như Robot, Stone và Treasure. Trên đó định nghĩa chức năng xử lý thông điệp (để nhận biết một đối tượng thuộc loại nào) cũng như các đặc tính chung mà mọi đối tượng 2D đều có như vị trí (position), màu sắc (color), … . Ở đây Stone đại diện cho vật cản trong môi trường (có thể là sông, suối, đá, rừng cây, …). Treasure đại diện cho đối tượng mà Robot cần tìm (chẳng hạn như kho báu). Lớp Robot, Stone và Treasure đều thuộc loại Object2D trong đó Robot với nhiệm vụ chính là tìm kiếm mục tiêu thỏa mãn yêu cầu của chúng ta. Để Robot có thể tiếp cận mục tiêu cũng như nhận thức được môi trường xung quanh, ta trang bị cho nó một camera (thuộc lớp Camera). 1.2 Biểu đồ cộng tác: Ý nghĩa: Robot tương tác với các đối tượng trong môi trường bằng cách sử dụng một Camera để quan sát các đối tượng xung quanh. Các đối tượng trong môi trường có thể xử lý các thông điệp do Robot gửi đến. Cụ thể là Robot phát tín hiệu đến các đối tượng và nhận các thông tin phản hồi để xác định đối tượng là Stone hay Treasure … . 2. Thiết kế mức cài đặt: Những khó khăn gặp phải và hướng giải quyết khi chuyển từ ý tưởng sang cài đặt: Để biết được các đối tượng nào lọt vào khung nhìn của Robot ta phải có sẵn một tập các đối tượng (tọa độ của chúng không chồâng lên nhau). Các đối tượng này do chương trình kiểm soát và chương trình không cung cấp hết thông tin về mọi đối tượng cho Robot mà chỉ cung cấp thông tin về những đối tượng nào lọt vào khung nhìn. Để giải quyết vấn đề này ta tạo ra một loại đối tượng tạm gọi là Controller với chức năng là quản lý các đối tượng và cung cấp thông tin về những đối tượng nào lọt vào khung nhìn của Robot. Robot không biết đến sự có mặt của Controller. Để giải quyết vấn đề này ta coi như Camera biết có Controller với ý nghĩa là nó có thể yêu cầu thông tin về đối tượng trong vùng nhìn từ Controller. Robot có thể đi vào những đường không đi tiếp được. Do đó có những lúc nó phải quay lui. Để giải quyết vấn đề quay lui ta buộc phải lưu vết đường đi. Theo nguyên tắc lập trình hướng đối tượng thì tất cả đều là đối tượng. Trong đề tài này, đường đi được hình thành từ các khoảng trống cho nên ta tạo ra một lớp Empty đại diện cho các đối tượng khoảng trống. Việc ta tạo đối tượng khoảng trống cũng không có gì là sai bởi lẽ khoảng trống cũng chứa thông tin (trống ở đâu) và cũng có khả năng xử lý thông điệp (không phản hồi thông tin – trong cài đặt ta cho nó phản hồi về NULL). 2.1 Sơ đồ lớp: Với yêu cầu của đề tài, sơ đồ lớp được thiết kế như sau: Mối quan hệ giữa các lớp: Robot có một Camera, lớp Camera có một CameraView và lớp Camera này biết có một Controller. Lớp Controller này quản lý một tập các đối tượng Object2D gồm Treasure, Stone và Empty. Ý nghĩa: Robot thu thập thông tin bằng cách yêu cầu Camera chụp hình và gởi về một tập các đối tượng lọt vào khung nhìn. Camera có được thông tin về đối tượng bằng cách tạo một khung nhìn (CameraView) và gởi yêu cầu cho Controller để có được các đối tượng lọt vào khung nhìn. Controller sẽ thực hiện việc xén dựa vào khung nhìn để lấy các đối tượng trong khung nhìn trả về cho Camera. Khi đó Camera sẽ gửi thông tin này cho Robot. Như vậy, ta có thể nói rằng Robot chưa biết thông tin về sự xuất hiện của các đối tượng trong môi trường mà phải đi đến đâu mới biết đến đó. Cơ chế phản hồi thông tin của các đối tượng trong môi trường: Trong thực tế, ta truyền thông điệp bằng cách phát tín hiệu, ví dụ như chiếu bằng tia sáng, và nhận thông tin phản hồi là quang phổ của đối tượng. Dựa vào quang phổ của đối tượng ta có thể xác định đối tượng thuộc loại nào. Trong phạm vi của đề tài này, ta không cài đặt thêm lớp chuyên về phân tích quang phổ mà ta cho các đối tượng phản hồi thông điệp là loại của đối tượng. Chỉ có một trường hợp đặc biệt là các đối tượng Empty không phản hồi thông tin (trả về NULL). Khi đó, dựa vào thông tin phản hồi ta có thể biết được đối tượng thuộc loại nào (Empty hay Non-Empty). Thực tế là có khả năng có những đối tượng mới mà ta chưa có thông tin về quang phổ. Trong cài đặt nếu gặp những đối tượng mới ta coi như nó cũng là vật cản. 2.2 Sơ đồ cộng tác: Toàn bộ quá trình tương tác được thực hiện thông qua các phương thức sau của Robot: void MyRobot::getObjectInfo() { getNextDir(); //xác định hướng quan sá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){ // hàm friend củ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) //gặp khoảng trống *oldType = EMPTY; else switch(*objType){ case TREASURE: RB->predictedPos = obj->position; RB->found = true; *oldType = EMPTY; //có thể đi được break; case STONE: *oldType = STONE; break; default: *oldType = UNKNOWN; } //đến nơi dự đoán nhưng chưa gặp if(RB->predictedPos == obj->position && (objType == NULL || RB->found == false)) RB->GetNewPredictPos(); //đoán điểm khác } extern Controller controller; ObjectList* Camera::ViewableObjects(MessageInfo* info) { return controller.ObjectsInView(this->CreateView()); } 2.3 Cấu trúc của lớp Robot: Các thuộc tính: objectInfo: mảng 2 chiều với số phần tử tối đa Robot có thể lưu trữ thông tin về loại đối tượng cũng như để tìm kiếm. predictedPos: vị trí dự đoán hiện tại. searchedDir: các hướng đã quan sát ở vị trí hiện tại. maxSearchDir: hướng quan sát tối đa có thể có. Các phương thức: Cá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); } Các phương thức nội bộ: 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){// góc 1/8 CPoint p[3]; //tính hai điểm kề dựa vào vị trí và hướng posFromDirect(x, y, p); //cấm vượt qua khe hẹ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ơ đồ lớp với các thuộc tính: Object2D: position: vị trí hiện tại của đối tượng. Để tăng tốc độ thực thi, ở đây ta cho nó là public với ý nghĩa là có thể lấy thông tin trực tiếp mà không phải gọi phương thức getPosition. Tuy nhiên, để thiết lập vị trí ta nên gọi phương thức setPosition nếu không thì chương trình có thể chạy sai so với ý muốn. color: màu sắc của đối tượng. Camera: Tất cả các thuộc tính đều là public vì như thế Robot dễ thao tác hơn mà không phải gọi các phương thức get và set. bShow: hiện khung nhìn. position: chính là vị trí của Robot. directionPos: một trong 8 hướng nhìn của Robot. angle: phân nửa góc nhìn của khung nhìn. radius: bán kính tầm nhìn. CameraView: Để đơn giản hoá vấn đề ta coi như khung nhìn có hình tam giác cân với đỉnh là vị trí của Robot. position[4]: 3 đỉnh tam giác và 1 điểm là trung điểm cạnh đáy. Controller: m_bHasObjects: Controller có đối tượng để quản lý. 2.5 Sơ đồ tìm kiếm: Giải thích: Init State: khởi tạo một số thông số của quá trình tìm kiếm. Ready: Trạng thái sẵn sàng (có khả năng gặp đối tượng cần tìm). Ready1: Trạng thái sẵn sàng (không có khả năng gặp đối tượng cần tìm). Found?: có gặp (đi đến) đối tượng cần tìm chưa? Update Heuristic: Học (lưu thông tin về vị trí của đối tượng cần tìm) CanGo?: có thể đi được (xung quanh nó có ít nhất một khoảng trống chưa đi qua)? Go: đi một bước (theo hướng đi được) AllDirSearched?: Tất cả các hướng có thể quan sát đều đã quan sát? CanReturn?: Có thể quay lui (danh sách điểm đã đi không rỗng)? Return: quay lui một bước (đến nơi trước đó, xóa điểm hiện tại khỏi danh sách điểm đã đi). GetDirectionInfo: Xác định hướng nào cần quan sát tiếp. GetViewableObject: Các đối tượng nào lọt vào khung nhìn đang quan sát. UpdateSearchedInfo: cập nhật thông tin về hướng đã quan sát. UpdateStateInfo: Cập nhật thông tin về các đối tượng đã biết. 2.6 Sơ đồ tuần tự cho chức năng thu thập thông tin (chức năng nhận thức): Robot gửi yêu cầu đến Camera với thông tin về vị trí, hướng nhìn. Camera dựa vào thông tin có được sẽ tạo CameraView, gửi thông tin về view này cho Controller để yêu cầu danh sách các đối tượng trong view; Thông tin có được từ Controller sẽ được gửi trả về cho Robot. Controller khi nhận được thông điệp sẽ thực hiện lọc các đối tượng nào lọt vào trong view (xén hình chữ nhật - ma trận chứa đối tượng - vào đa giác) và gửi thông tin về những đối tượng đó về cho Camera (cụ thể là danh sách chứa các con trỏ chỉ đến các đối tượng). Các đối tượng vẫn do Controller kiểm soát (đúng hơn là dù các đối tượng có dời đi đâu đi chăng nữa Controller vẫn luôn có địa chỉ của chúng miễn là chúng còn sống – ta không delete chúng). Dựa vào danh sách các đối tượng có được từ Camera, Robot sẽ lần lượt phân tích thông tin về loại đối tượng (bằng cách gửi thông điệp đến các đối tượng và nhận thông tin phản hồi) để xác định các loại đối tượng nào lọt vào khung nhìn (cập nhật thông tin về loại đối tượng). 2.7 Các lớp tiện ích: Giải thích: Cấu trúc sData được dùng để chứa thông tin kiểu T (một loại lớp chưa biết). Nó có con trỏ next có thể trỏ đến kiểu sData. Lớp sData là lớp chuyên biệt của lớp sData với thông tin về kiểu là T. Lớp CStack là stack dùng để chứa các đối tượng thuộc kiểu T. Nó có một con trỏ tail thuộc kiểu sData. Lớp CStack là lớp chuyên biệt của lớp CStack với thông tin về kiểu là Object2D. Lớp ObjectList dùng stack để chứa các đối tượng Object2D. Nó có một con trỏ list thuộc kiểu CStack. Lớp CStack là lớp chuyên biệt của lớp CStack với thông tin về kiểu là PositionInfo. Lớp PositionInfoList dùng stack để chứa các đối tượng PositionInfo. Nó có một con trỏ list thuộc kiểu CStack. Hàng đợi ưu tiên: Giải thích: Lớp PriorityQueue dùng để chứa các hướng đi có thể có của Robot từ vị trí hiện tại với độ ưu tiên dựa vào độ lệch so với điểm dự đoán. Nó có một con trỏ items dùng để trỏ đến phần tử đầu tiên của danh sách ưu tiên. Mỗi phần tử của danh sách ưu tiên chứa vị trí, độ ưu tiên và một con trỏ next để trỏ đến phần tử kế tiếp trong danh sách. Phần tử cuối cùng sẽ không trỏ đến đâu cả (trỏ đến NULL). Phương thức remove được dùng để lấy phần tử đầu khỏi danh sách (phần tử kế tiếp nếu có sẽ là phần tử đầu của danh sách). Phương thức add dùng để thêm một phần tử (có thông tin về vị trí và độ ưu tiên) vào danh sách ở vị trí thích hợp. Trong trường hợp có nhiều phần tử cùng độ ưu tiên thì trật tự của chúng là ngẫu nhiên. KẾT LUẬN VÀ HƯỚNG MỞ RỘNG Sau một thời gian thực hiện, đến nay đề tài cơ bản đã hoàn thành nhiệm vụ được giao. Cụ thể là phần tìm hiểu công nghệ, em đã vận dụng các công nghệ được yêu cầu vào đề tài và chương trình ứng dụng minh họa về cơ bản đã hoàn thành. Tuy nhiên, do trình độ chuyên môn cũng như kinh nghiệm còn hạn chế nên việc ứng dụng các công nghệ vào đề tài chưa thật sự tốt lắm. Cụ thể là kỹ thuật Camera tổng hợp chưa được phát huy hết khả năng mà đề tài chỉ có thể sử dụng được một ít tính năng của nó. Bên cạnh đó, việc vận dụng các kỹ thuật của trí tuệ nhân tạo vào đề tài cũng còn nhiều hạn chế nên chưa thể làm cho Robot có khả năng thông minh cao. Các hướng cần được mở rộng của đề tài là: Vận dụng tốt hơn tiếp cận Camera tổng hợp vào quá trình nhận thức để việc mô phỏng khả năng “nhìn” của Robot thực tế hơn. Khả năng học của Robot cần được cải thiện để Robot có thể “thông minh” hơn trong việc tìm kiếm như tránh né chướng ngại vật, chọn hướng đi tốt, dự đoán vị trí của vật cần tìm chính xác hơn…. Trong tương lai, khi có đủ thời gian, nhân lực cũng như công nghệ thì em hy vọng đề tài này sẽ được phát triển hoàn thiện hơn nữa để có thể trở thành một công cụ đắc lực trong việc thiết kế Robot .