Khóa luận Xây dựng và đánh giá một hệ thống mô phỏng giao thông Việt Nam - Ngô Đức Hải

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Ngô Đức Hải XÂY DỰNG VÀ ĐÁNH GIÁ MỘT HỆ THỐNG MÔ PHỎNG GIAO THÔNG VIỆT NAM KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ Thông tin HÀ NỘI - 2010 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Ngô Đức Hải XÂY DỰNG VÀ ĐÁNH GIÁ MỘT HỆ THỐNG MÔ PHỎNG GIAO THÔNG VIỆT NAM KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ Thông tin Cán bộ hướng dẫn: PGS.TS. Bùi Thế Duy HÀ NỘI - 2010 TÓM TẮT KHOÁ LUẬN Từ lâu, việc phát triển một hệ thống mô phỏng giao thông đã được nhiều nhà nghiên cứu trên thế giới quan tâm và đã đạt được một số thành tựu nhất định. Những thành tựu này cũng đã đóng góp phần nào vào sự phát triển của hệ thống giao thông ở các nước tiên tiến. Tuy nhiên, việc ứng dụng các thành tựu này vào giao thông Việt Nam là rất khó khăn do cơ sở vật chất, cơ sở hạ tầng giao thông của nước ta có nhiều khác biệt, cùng với đó là sự khác nhau về các loại phương tiện tham gia giao thông và ý thức của người tham gia giao thông. Vì vậy việc nghiên cứu một hệ thống mô phỏng giao thông thích hợp với Việt Nam là rất cần thiết và đã được chúng tôi chọn làm đề tài để thực hiện khóa luận này. Đầu tiên, chúng tôi sẽ đưa ra một số cơ sở lý thuyết cho việc mô phỏng giao thông. Trong số đó chúng tôi sẽ đi sâu vào phương pháp mô phỏng dựa trên agent, một công nghệ rất thích hợp để mô phỏng một mô hình có sự tương tác cá thể - cá thể và cá thể - môi trường giống như mô hình giao thông. Cuối cùng, chúng tôi sẽ trình bầy về hệ thống mô phỏng giao thông Việt Nam mà chúng tôi đã nghiên cứu và xây dựng và các kết quả đạt được qua quá trình này. LỜI CÁM ƠN Đầu tiên, em xin gửi lời cám ơn tới các thầy cô của trường Đại học Công Nghệ - Đại học Quốc Gia Hà Nội đã tận tình hướng dẫn, chỉ bảo em trong quá trình học tập và làm việc những năm học vừa qua. Em xin gửi lời cám ơn chân thành tới Phó Giáo sư Tiến sĩ Bùi Thế Duy, người đã tận tình hướng dẫn em trong suốt thời gian thực hiện khóa luận. Em vô cùng biết ơn bố mẹ, những người đã có công sinh thành, nuôi dậy và luôn luôn tin tưởng, ủng hộ em. Em cũng xin gửi lời cám ơn tới các anh chị em và mọi người trong gia đình cùng bạn bè vì đã luôn tin cậy, động viên và giúp đỡ em trong cuộc sống. Hà Nội, ngày 2 tháng 5 năm 2010 Sinh viên Ngô Đức Hải MỤC LỤC MỘT SỐ THUẬT NGỮ MAS Multi-Agent System Hệ thống đa Agent ABM Agent-Based Modeling Mô hình dựa trên Agent DANH SÁCH HÌNH VẼ & BẢNG BIỂU Hình 1-1: Hệ thống mô phỏng giao thông trực quan 4 Hình 1-2: Chức năng thống kê của của hệ thống mô phỏng trực quan 4 Hình 1-3: Hệ thống mô phỏng đường cao tốc 7 Hình 1-4: Mô tả cấu tạo đoạn đường cao tốc 8 Hình 1-5: Hệ thống mô phỏng đèn giao thông 9 Hình 2-1: Ưu việt của agent so với đối tượng 14 Hình 3-1: Chia một ngã tư gồm nhiều tuyến đường thành các vùng đơn giản 17 Hình 3-2: Vùng ở giữa ngã tư chứa nhiều tuyến đường khác nhau 18 Hình 3-3: Các lối vào, lối ra và các đoạn đương trong một vùng 18 Hình 3-4: 16 đoạn đường ở vùng giữa ngã tư 19 Hình 3-5: Thuộc tính vận tốc an toàn ảnh hưởng đến cách lái xe của các agent 23 Hình 3-6: Thuộc tính thời gian dự tính ảnh hưởng đến cách lái xe của các agent 24 Hình 3-7: Biểu đồ mô tả các thành phần của hệ thống và mối quan hệ của chúng 25 Hình 3-8: Thuật toán tính toán di chuyển của agent 29 Hình 3-9: Agent lập kế hoạch lý tưởng trên đường dài và thẳng 30 Hình 3-10: Thuật toán xây dựng kế hoạch di chuyển lý tưởng của agent 31 Hình 3-11: Agent lập kế hoạch di chuyển lý tưởng trên hệ thống đường bất kỳ 32 Hình 3-12: Agent cảm nhận được va chạm với agent khác 33 Hình 3-13: Agent hình dung vị trí của agent khác ở các thời điểm dịch chuyển 33 Hình 3-14: Thuật toán kiểm tra va chạm nếu di theo chuyển theo kế hoạch lý tưởng 34 Hình 3-15: Agent kiểm tra lựa chọn đánh lái để tránh va chạm 35 Hình 3-16: Giao diện chương trình ở chế độ thiết kế 38 Hình 3-17: Ghép các vùng đường với nhau để tạo thành hệ thống đường xá tùy ý 39 Hình 3-18: Hộp thoại chọn các thành phần đường dựng sẵn 39 Hình 3-19: Hộp thoại tùy chọn số người tham gia giao thông 40 Hình 3-20: Hộp thoại tùy chọn các thuộc tính của người lái 40 Hình 3-21: Giao diện chương trình ở chế độ mô phỏng 41 Hình 3-22: Thử nghiệm mô phỏng tại môt ngã tư có bùng binh 42 Hình 3-23: Thử nghiệm mô phỏng với 80 người 44 Hình 3-24: Thử nghiệm mô phỏng với 120 người 45 Hình 3-25: Thử nghiệm mô phỏng với 160 người 46 Bảng 3-1: Thuộc tính của các người lái 43 Bảng 3-2: Thử nghiệm mô phỏng với 80 người 44 Bảng 3-3: Thử nghiệm mô phỏng với 120 người 45 Bảng 3-4: Thử nghiệm mô phỏng với 160 người 46 MỞ ĐẦU Đối với mọi quốc gia, giao thông là một bộ phận trong kết cấu hạ tầng, có ảnh hưởng trực tiếp đến sự phát triển kinh tế - xã hội. Ở các nước phát triển, việc phát triển hệ thống giao thông luôn được đầu tư những khoản chi phí khổng lồ. Bên cạnh đó, các nhà quy hoạch luôn có một tầm nhìn chiến lược, định ra được kế hoạch rõ ràng trong việc xây dựng các hệ thống giao thông. Nhờ vậy mà hệ thống giao thông của những nước này rất phát triển, tạo cơ sở thuận lợi cho sự phát triển của kinh tế và xã hội. Còn ở Việt Nam thì ngược lại, cơ sở hạ tầng giao thông không theo kịp sự phát triển kinh tế xã hội và dân số, gây cản trở cho sự nghiệp hiện đại hóa, công nghiệp hóa của đất nước. Hiện nay ở nước ta, giao thông đang là một vấn đề nhức nhối của các nhà hoạch định chính sách. Ở các đô thị như Hà Nội, nhiều hệ thống đường quá hỗn độn, không theo quy chuẩn hay quá chật hẹp. Trong khi đó, số lượng xe tham gia thông không ngừng gia tăng. Điều đó đã dẫn đến hậu quả là sự gia tăng về tắc đường, tai nạn, ô nhiễm môi trường. Thêm vào đó, ý thức của người tham gia giao thông chưa cao nên càng làm tăng tính phức tạp của giao thông Việt Nam. Vì vậy việc tìm giải pháp phát triển cho các hệ thống giao thông ở nước ta là rất khó khăn. Ở nhiều nước trên thế giới, việc mô phỏng hệ thống giao thông trên máy tính đã được nghiên cứu từ lâu nhằm phục vụ cho việc tìm kiếm và đánh giá các giải pháp phát triển hệ thống giao thông. Trước khi chặn một tuyến đường, mở một tuyến đường mới hay điều chỉnh thời gian bật đèn xanh, đèn đỏ ngoài thực tế, các nhà phát triển có thể thử trên hệ thống mô phỏng trước. Tuy nhiên, giao thông của Việt Nam là rất khác biệt và phức tạp nên việc ứng dụng các thành tựu nghiên cứu này là rất khó. Hơn nữa, mô phỏng giao thông vẫn còn là một đề tài ít được các nhà nghiên cứu trong nước quan tâm. Do đó chúng tôi đã nghiên cứu và xây dựng một hệ thống mô phỏng thích hợp với giao thông của Việt Nam nhằm phục vụ cho việc phát triển hệ thống giao thông trong nước. Mô phỏng thực chất là tái hiện hoặc tạo dựng một phần nào nào đó của thế giới thực trên máy tính. Đối với mô phỏng giao thông, đã có nhiều phương pháp, cơ sở lý thuyết được đưa ra. Chúng tôi đã chọn phương pháp mô phỏng dựa trên agent làm phương pháp nghiên cứu và xây dựng một hệ thống mô phỏng giao thông. Với các mô hình có sự tương tác giữa các cá thể như hệ thống giao thông thì việc sử dụng mô hình dựa trên agent là rất thích hợp. Đây là một phương pháp tiên tiến và đã được ứng dụng nhiều trong việc mô phỏng các hệ thống phức tạp trong thực tế. Hệ thống mô phỏng giao thông mà chúng tôi xây dựng cho phép người sử dụng có thể tùy biến tạo ra các hệ thống giao thông đa dạng, phức tạp, rồi quan sát sự di chuyển của các phương tiện trên hệ thống giao thông này. Từ việc quan sát này mà các nhà quy hoạch giao thông có thể đánh giá được các giải pháp phát triển hệ thống giao thông và đưa ra quyết định của mình. Nội dung của khóa luận gồm 4 chương: Chương 1 sẽ trình bầy về bài toán mô phỏng giao thông và các mô hình mô phỏng giao thông của các nhà nghiên cứu trên thế giới trước đây Chương 2 sẽ trình bầy về agent, hệ thống đa agent, phương pháp sử dụng mô hình dựa trên agent và các ứng dụng của mô hình này. Chương 3 sẽ trình bầy về hệ thống mô phỏng giao thông mà chúng tôi đã nghiên cứu và xây dựng. Cuối cùng, Chương 4 sẽ tổng kết các kết quả đã đạt được và hướng phát triển hệ thống mô phỏng giao thông trong tương lai. CHƯƠNG 1: MÔ PHỎNG GIAO THÔNG 1.1. Giới thiệu Việc phát triển hệ thống giao thông tốt là nhu cầu bức thiết của mỗi quốc gia nhằm tạo cơ sở thuận lợi cho quá trình phát triển kinh tế xã hội. Xây dựng được một hệ thống giao thông tốt là một bài toán khó với các nhà quy hoạch giao thông. Ngoài việc phân tích, đánh giá mang tính lý thuyết, họ cần có một cái nhìn trực quan về các giải pháp mà họ lựa chọn. Tuy nhiên, không phải lúc nào cũng có thể áp dụng các giải pháp phát triển hệ thống giao thông vào thực tế chỉ để kiểm tra tính hiệu quả do nhiều nguyên nhân như tốn kém, mất nhiều thời gian, hoặc gặp rủi ro không lường trước được. Chính vì vậy, họ cần một công cụ giúp họ mô phỏng các giải pháp phát triển hệ thống giao thông để đánh giá và đưa ra lựa chọn hợp lý nhất. Công cụ mô phỏng giao thông đầu tiên được ra đời năm 1955 [10], và kể từ đó đến nay, việc mô phỏng giao thông trên máy tính đã được nghiên cứu, phát triển và được áp dụng nhiều vào thực tế. Đã có rất nhiều công cụ được ra đời, nhiều giải pháp, cơ sở lý thuyết được đưa ra. Có những giải pháp mang tính vĩ mô, các nhà nghiên cứu chỉ để tâm đến mối liên hệ giữa các tham số như vận tốc các, lưu lượng, mật độ các xe tham gia giao thông. Các giải pháp mang tính vi mô thì nhằm xây dựng các hệ thống mô phỏng mà có sự chuyển động của các xe một cách chi thiết. Có những giải pháp mang tính rời rạc hay liên tục về thời gian… Tính đến nay, việc nghiên cứu xây dựng công cụ mô phỏng giao thông đã đạt được nhiều thành tựu, đã đóng góp phần nào vào sự phát triển của các hệ thống giao thông ở nhiều nước tiên tiến trên thế giới. Tuy nhiên, rất khó có thể ứng dụng được những công cụ này để mô phỏng hệ thống giao thông ở Việt Nam do hệ thống giao thông của nước ta có nhiều điểm khác biệt. Cơ sở hạ tầng giao thông còn kém, hệ thống giao thông mang tính phức tạp vì có nhiều hệ thống đường xá chằng chịt trong một diện tích nhỏ, nhất là trong các đô thị. Hầu hết các công cụ mô phỏng được xây dựng chỉ mô phỏng các phương tiện đi trên đường là ô tô. Trong khi đó, các phương tiện tham giao ở nước ta rất hỗn tạp, từ những phương tiện kích thước nhỏ xe đạp, xe máy đến những phương tiện cỡ lớn như ô tô, xe tải, xe buýt, hay thậm chí là các phương tiện thô xơ. Thêm vào đó sự thiếu ý thức chấp hành luật lệ giao thông của người lái xe là chưa cao nên càng làm cho hệ thống giao thông thêm hỗn độn. Chính vì vậy mà nghiên cứu một hệ thống mô phỏng chi tiết giao thông của nước ta là rất cần thiết. Đó là nguyên nhân thúc đẩy chúng tôi nghiên cứu một hệ thống mô phỏng giao thông phù hợp với tình hình giao thông ở Việt Nam. Nhưng trước khi trình bầy những những nghiên cứu và các kết quả đã đạt được, chúng tôi xin được giới thiệu một số phương pháp, cơ sở lý thuyết và các công cụ mô phỏng hệ thống giao thông của các nhà nghiên cứu trước đây. 1.2. Hệ thống mô phỏng giao thông trực quan Đây là hệ thống được nghiên cứu và phát triển bởi Thomas Fotherby [14]. Hệ thống rất đa năng trong việc mô phỏng các hệ thống giao thông. Nó cung cấp các chức năng thiết kế mạng lưới giao thống, hệ thống mô phỏng các xe chạy trên mạng lưới giao thông đã được thiết kế và một chức năng rất hữu ích đó là chức năng thống kê chi tiết các thông số như lưu lượng xe đi trên đường, vận tốc trung bình các xe, …Vì vậy mà hệ thống này được coi là tiếp cận từ cả hai hướng là theo hướng vi mô và theo hướng vi mô. (a) Chế độ thiết kế (b) Chế độ mô phỏng Hình 1-1: Hệ thống mô phỏng giao thông trực quan Hình 1-2: Chức năng thống kê của của hệ thống mô phỏng trực quan Hệ thống được xây dựng dựa trên các 3 mô hình cơ bản bao gồm mô hình hệ thống giao thông, mô hình điều khiển sự di chuyển các xe trên đường, mô hình thống kê. 1.2.1. Mô hình hệ thống giao thông Đây là hệ thống mô tả mạng lưới đường đi. Mạng lưới này được xây dựng từ các thành phần gồm đoạn đường thẳng - Road và vùng đường giao nhau – Junction: Mỗi đoạn đường thẳng được mô tả bằng hai đoạn thẳng song song với nhau, cách nhau một khoảng đúng bằng độ rộng của một làn đường dành cho ô tô và có một điểm đầu và một điểm kết thúc. Mỗi đoạn đường này đều có một hướng nhất định xác định bởi điểm đầu và điểm cuối. Khi nối các đoạn đường này với nhau theo cùng một hướng ta sẽ được một tuyến đường gấp khúc tùy ý. Khi xếp các đoạn đường này song song ta sẽ đường một tuyến đường đi thật sự có độ rộng bằng số nguyên lần độ rộng của một làn đường. Mỗi vùng đường giao nhau được mô tả bằng một hình chữ nhật có chiều dài và chiều rộng bằng số nguyên lần độ rộng của một làn đường, tối đa là gấp 4 lần làn đường. Trên mỗi cạnh của vùng này có các điểm nối. Khi nối các đoạn đường nêu trên vào các điểm nối này ta sẽ được hệ thống các đường giao nhau. Hơn nữa, các vùng giao nhau này có các thuộc tính giúp mô tả các đèn giao thông, đường ưu tiên, giúp xây dựng các luật đi đơn giản trên đưòng. Về mặt giao diện, hệ thống cung cấp công cụ thiết kế một cách trực quan mạng lưới giao thông. Về mặt phát triển, nó cung cấp một thư viện lệnh giúp người phát triển có thể thao tác dễ dàng với các thành phần này để tạo ra các mạng lưới giao thông bằng cách lập trình. 1.2.2. Mô hình điều khiển sự di chuyển các xe trên đường Đây là mô hình giúp tính toán sự di chuyển từng xe tham gia giao thông. Mô hình này có các thành phần nhỏ hơn. Chúng bao gồm bộ đếm thời gian để thực hiện việc lái xe chân thực, thành phần sinh xe ngẫu nhiên tại một đầu vào của hệ thống giao thông, và thành phần quan trọng của mô hình này là thành phần tính toán sự di chuyển của các xe. Cách thức di chuyển các xe được mô tả như sau: Trường hợp xe đang đi trên đoạn đường thẳng: Gọi v là vận tốc của xe trên đường, x là khoảng cách với xe gần nhất phía trước, thì vận tốc v sẽ được xác định như sau: k, nếu v ≥ L giá trị giữa 0 và k, nếu l < v < L 0, nếu x ≤ L Trong đó k là vận tốc lớn nhất xe có thể đạt được, L là khoảng cách an toàn với xe phía trước, l là khoảng cách nguy hiểm với xe ở phía trước. Khi đi đến gần đoạn đường giao nhau, xe có các lựa chọn sau: Dừng lại khi gặp đèn đỏ Nếu có xe ở hướng khác và có độ ưu tiên cao hơn thì giảm tốc độ, nhường xe ở phía này đi qua Nếu có xe ở hướng khác đi tới nhưng xe đang ở đoạn đường ưu tiên cao hơn thì xe có thể đi tiếp, nhưng lúc này xe cần điều chỉnh tốc độ để không va chạm với các xe khác đang nằm trong vùng đường giao nhau này 1.2.3. Mô hình thống kê Đây là mô hình giúp ghi lại các thông tin của các xe đi trên đường. Tại một thời điểm trong một chu kỳ nào đó, mô hình này sẽ ghi lại số lượng xe vào và ra khỏi hệ thống, số lượng xe đang di chuyển, vận tốc trung bình các xe, … Các thông tin này có thể được xem là hữu ích để đánh giá mức độ hợp lý của hệ thống giao thông. Đây có thể coi là công cụ khá thích hợp trong việc mô phỏng các hệ thống giao thông đô thị. Trong phần tới, chúng tôi sẽ giới thiệu một hệ thống dùng để mô phỏng một loại hệ thống giao thông khác, đó là hệ thống mô phỏng giao thông trên đường cao tốc. 1.3. Mô phỏng xe thông minh trên đường cao tốc Đây là một hệ thống mô phỏng giao thông đưa ra bởi Rahul Sukthankar, Dean Pomerleau và Charles Thorpe [13]. Hệ thống này mang tên Simulated Highways for Intelligent Vehicle Algorithms (viết tắt là SHIVA) và chủ yếu dùng để mô phỏng giao thông trên đường cao tốc ở mức độ vi mô. Đường cao tốc thường có độ dài lớn, mật độ đèn giao thông là rất ít, và các nhà trong hệ thống này được coi như là không có. Tốc độ di chuyển các xe trên đường cao tốc là rất cao, chính vì vậy mà hệ thống được chú trọng vào việc tính toán sự di chuyển quả các xe một cách tiết để đánh giá được mức độ an toàn của một đường cao tốc. Hình 1-3: Hệ thống mô phỏng đường cao tốc Hệ thống chỉ gồm 2 mô hình chính là mô hình mạng lưới đường cao tốc và mô hình xe cộ. 1.3.1. Mô hình mạng lưới đường cao tốc Mô hình này mô tả một mạng lưới đường cao tốc với các đoạn đường dài ghép nối với nhau. Thành phần cơ bản của mô hình này là các đoạn đường, được gọi là RoadSegment. Khác với hệ thống mô phỏng giao thông trực quan của Thomas Fotherby [14], các đoạn đường có hình dạng rất tùy ý, nhưng độ rộng luôn phải bằng số nguyên lần độ rộng một làn đường được mô tả bằng “lane number”. Ngoài ra, nó còn chứa thông tin mô tả về đoạn bị thu hẹp (RoadSlice), các mối nối để nối nhiều đoạn đường thẳng với nhau, và tốc độ tối đa các xe khi di chuyển trên đoạn đường đó. Hình 1-4: Mô tả cấu tạo đoạn đường cao tốc 1.3.2. Mô hình xe cộ Đây là mô hình khá phức tạp, gồm các thành phần: thành phần lệnh điều khiển, thành phần cảm ứng và thành phần người lái xe. Thành phần lệnh điều khiển – Controller. Đây là thành phần mô tả các lệnh điều khiển của người lái xe bao gồm: Đánh lái: Dùng để mô tả lệnh đánh lái khi lái xe của người điều khiển. Nó gồm các thông tin mô tả như đánh lái về phía nào, bao nhiêu độ, … Điều chỉnh tốc độ: Mô tả lệnh tăng tốc, giảm tốc hoặc giữ tốc độ của người lái xe Thành phần cảm ứng: Đây là thành phần giúp xe cảm giác được sự di chuyển của các xe khác chẳng hạn như tăng tốc, giảm tốc, đang đổi hướng. Điều này làm cho việc điều khiển không bị cứng nhắc như điều khiển sự di chuyển của xe trong hệ thống mô phỏng trực quan của Thomas Fotherby [14]. Thành phần người lái xe: Đây là thành phần tính toán ra quyết định của người lái xe. Trong một tập lệnh điều khiển được đưa ra, dựa vào các thông tin lấy từ thành phần cảm ứng, một thuật toán sẽ được thực thi để tính toán quyết định chọn cách điều khiển hợp lý nhất của người lái. Hệ thống cho phép người định nghĩa các loại xe khác nhau như xe tải, xe con, công-ten-nơ. Người sử dụng không chỉ có thể định nghĩa kích thước của xe mà còn có thể mô tả các tham số khác như khả năng tăng tốc, giảm tốc, tốc độ đổi hướng, … Việc định nghĩa này có thể thực hiện qua việc chỉnh sửa file cài đặt ( config file ). 1.4. Hệ thống mô phỏng đèn giao thông Trong mục này, chúng tôi xin giới thiệu về hệ thống mô phỏng đèn giao thông được phát triển bởi một số thành viên của trường đại học Utrecht (Hà Lan) [7]. Đây là một hệ thống khá thông minh trong việc trợ giúp lựa chọn thời gian bật đèn xanh đèn đỏ của đèn giao thông. Hình 1-5: Hệ thống mô phỏng đèn giao thông Về cơ bản đây cũng là một hệ thống mô phỏng giao thông vi mô. Tuy nhiên, nó có chức năng thống kê các thông tin như lượng xe qua lại, vận tốc trung bình các xe. Thông tin này không chỉ mang tính tham khảo, mà nó còn được sử dụng bên trong hệ thống để tự động điều chỉnh thời gian bật đèn xanh, đèn đỏ của các đèn giao thông sao cho hợp lý. Các thành phần chính của hệ thống này gồm: Các làn đường (DriveLane) được mô tả bởi 2 đoạn thẳng song song. Các đoạn đường (Road) được tạo từ 2 làn đường. Nó có thêm thông tin về chiều, đầu vào đầu ra dùng để liên kết tạo thành mạng lưới giao thông. Các nút (Node) mô tả các đường giao nhau như ngã tư, ngã ba. Đây chính là các ô vuông màu xám trong hình 5. Các nút chứa thông tin về các đầu vào và đầu ra dùng để nối với các đoạn đường để tạo ra mạng lưới giao thông. Các nút biên (EdgeNode) mô tả các khu vực mà xe cộ xe đi vào và đi ra. Đây chính là các ô vuông màu xám trong hình 5. Các tín hiệu đèn (Sign) mô tả đèn giao thông. Nó chứa một số thông tin dùng trong giải thuật điều chỉnh thời gian bật đèn xanh, đèn đỏ sao cho hợp lý một cách tự động. Thành phần xe cộ (Car) đóng vai trò phương tiện tham gia giao thông trong hệ thống này. Vì hệ thống chỉ tập trung vào cách thức tự động điều chỉnh tín hiệu đèn sao cho hợp lý nên cách di chuyển của các xe là khá đơn giản. Trong quá trình mô phỏng, hệ thống thực hiện việc thống kê một số thông tin như mật độ xe, lượng xe qua lại, … Các thông tin này được sử dụng làm tham số cho giải thuật điều chỉnh thời gian bật đèn xanh, đèn đỏ. 1.5. Kết luận Chúng tôi vừa trình bầy một số hệ thống mô phỏng giao thông tiêu biểu. Các hệ thống này có một số điểm chung. Thứ nhất, chúng đều là các hệ thống mô phỏng giao thông vi mô, tức là đều cố gắng mô phỏng một cách chi tiết sự di chuyển của các phương tiện tham gia giao thông. Thứ hai, các hệ thống này đều cho phép tạo ra các mạng lưới giao thông một cách linh hoạt, tuy nhiên vẫn rất khó để tạo dựng lại một mạng lưới giao thông Việt Nam do sự phức tạp của mạng lưới giao thông nước ta. Một điểm chung nữa là các phương tiện tham gia giao thông trong các hệ thống này chủ yếu là ô tô, sự di chuyển không quá phức tạp để tính toán. Như đã đề cập, hệ thống giao thông của nước ta khá phức tạp với hệ thống đường chằng chịt, các phương tiện giao thông nhiều chủng loại, hỗn tạp. Thêm vào đó, sự thiếu ý thức của người tham gia giao thông đã làm cho hệ thống giao thông trở nên rất hỗn độn. Vì vậy mà rất khó có thể áp dụng những hệ thống mô phỏng này vào giao thông của nước ta. Do đó, việc xây dựng một hệ thống mô phỏng chi tiết hơn cho giao thông Việt Nam là rất cần thiết. Tuy nhiên, những hệ thống nêu trên cũng có một số ưu điểm nhất định. Bên cạnh việc tiếp thu những cơ sở lý thuyết, phương pháp xây dựng của các hệ thống này, chúng tôi đã kết hợp sử dụng phương pháp mới nhằm nghiên cứu xây dựng một hệ thống mô phỏng giao thông phù hợp hơn với tình hình giao thông của Việt Nam. Phương pháp mà chúng tôi muốn đề cập ở đây là sử dụng mô hình dựa đa agent. Đây là mộ phương pháp tiên tiến trong việc mô phỏng các mô hình có sự tương tác giữa cá thể với môi trường và giữa các cá thể với nhau. Trong chương tiếp theo, chúng tôi sẽ trình bầy kỹ về agent, hệ thống đa agent, phương pháp mô phỏng dựa trên agent và một số ứng dụng của công nghệ này. CHƯƠNG 2: MÔ HÌNH DỰA TRÊN AGENT 2.1. Agent và hệ thống đa agent Agent là một khái niệm tương đối mới và hiện nay được rất nhiều các nhà nghiên cứu quan tâm. Dưới đây chúng tôi xin trình bầy một số khái niệm và đặc điểm của agent và hệ thống đa agent. 2.1.1. Agent Có rất nhiều khái niệm về agent đã được đưa ra nhưng cho đến nay vẫn chưa có một khái niệm được coi là chung nhất cho agent. Chúng tôi xin nêu một khái niệm được đưa ra bởi Wooldridge và Jennings [11]: “Một agent là một hệ thống máy tính được đặt trong một môi trường nào đó, và nó có khả năng hành động một cách tự chủ trong môi trường này nhằm đạt được một mục tiêu nào đó” Để mô tả kỹ hơn về agent, chúng tôi xin trình bầy một số đặc điểm của nó: Mỗi agent trong môi trường đều có những thuộc tính riêng biệt. Chúng cảm nhận, tiếp thu thông tin từ môi trường rồi đưa ra hành động dựa vào trạng thái hiện thời của các thuộc tính của chúng. Mỗi agent có một số nguyên tắc chi phối hành vi và khả năng đưa ra quyết định của chúng [4] Agent có khả năng đáp ứng lại sự tác động từ môi trường bằng cách đưa ra hành động nào đó. Tuy nhiên, agent không chỉ đưa hành động có tính đáp ứng mà các hành động của agent còn hướng đến mục tiêu nào đó. Để đạt được mục tiêu, các agent cần thực hiện một chuỗi các hành động khác nhau. Việc xác định chuỗi các hành động cần thực hiện chính là lên kế hoạch [6]. Agent có tính chủ động. Chúng có khả năng tự đưa ra hành động, hoạt động một cách độc lập mà không chịu sự chi phối, tác động hay kích thích từ các yếu tố bên ngoài. Agent có tính linh động. Chúng có khả năng học hỏi, ghi nhớ và đưa ra các hành vi đáp ứng dựa trên những kinh nghiệm của chúng [4]. Trên đây là một số đặc điểm chung của agent nhưng chưa đầy đủ. Để có thể mô tả được đầy đủ các đặc điểm của agent, ta phải đặt nó vào môi trường mà trong đó có sự tham gia của nhiều agent. Trong mục tiếp theo, chúng tôi xin giới thiệu về hệ thống đa agent và bổ sung một số đặc điểm khác của agent khi tham gia vào môi trường có sự có mặt của nhiều agent khác. 2.1.2. Hệ thống đa agent – MAS Một hệ thống đa agent, hay gọi tắt là MAS (Multi-Agent System), là một hệ thống trong đó có sự có mặt của của nhiều agent trong một môi trường và có sự tương tác lẫn nhau giữa chúng. Các agent có thể tương tác với nhau theo nhiều cách. Các hành động đưa ra của chúng có thể có tính cạnh tranh, xung đột với các agent khác. Hoặc chúng có thể hợp tác, phối hợp hành động để đạt được mục tiêu hay thậm chí có thể cùng lên kế hoạch hành động để đạt được mục tiêu chung nào đó [9]. Các agent có khả năng giao tiếp với các agent khác bằng cách truyền và nhận các thông điệp theo một giao thức nào đó. Thậm chí các agent có thể nhận biết được các agent khác tiếp nhận thông được tin gì [15]. Trong MAS, mỗi agent đều có một cái nhìn giới hạn, chúng không có thông tin đầy đủ về môi trường và các agent khác trong toàn bộ hệ thống [9]. Mỗi hành động của agent đều tác động tới một phần của môi trường và các agent khác trong một phạm vi nào đó. Trong một MAS, các hành vi của và thuộc tính của các agent là không đồng nhất. MAS có thể có tính tổ chức, tức là các agent có thể hoạt động trong một nhóm các agent nào đó, chúng có một số rằng buộc nào đó với nhau và các hoạt động của chúng sẽ nhắm đến một mục tiêu chung của nhóm. Có nhiều loại mô hình tổ chức trong MAS. Với loại mô hình phân cấp, quyền ra quyết định hành động thường nằm trong tay một agent đứng đầu ở mỗi cấp. Ở mô hình tổ chức này, các agent thường tương tác với các agent khác trong cùng cấp hoặc với các agent ở các cấp liền kề ( trên và dưới ). Một mô hình tổ chức khác là mô hình thị trường, trong đó có sự tồn tại của các agent đóng vai trò cung cấp sản phẩm hoặc dịch vụ và các agent đóng vai trò có nhu cầu sử dụng sản phẩm dịch vụ [1]. Một ví dụ điển hình về MAS chính là Internet [9]. Internet có thể được coi là một mạng lưới rộng lớn với mỗi nút của mạng lưới là một agent. Các nút mạng này được thiết kế, thực thi bởi những người, tổ chức khác nhau, và hoạt động với những mục đích khác nhau. Ngoài ra, hoạt động của chúng là không đồng bộ. Các nút mạng trao đổi thông tin với các nút mạng khác trong một phạm vi nào đó và theo một giao thức nào đó, … Trong một hệ thống giao thông, hệ thống đường xá, các đèn giao thông, tín hiệu giao thông đóng vai trò môi trường. Mỗi người tham gia giao thông trong đó đóng vai trò một agent. Các agent này đưa ra hành động bằng cách di chuyển theo các cách khác nhau để đạt được một mục tiêu là đi đến một vị trí nào đó trong hệ thống đường xá. Mỗi người tham gia giao thông đều có những thuộc tính riêng biệt phụ thuộc vào giới tính, tuổi tác, kinh nghiệm, … và do đó cách di chuyển của họ cũng là không đồng nhất. Người tham gia giao thông tương tác với những người khác trong một phạm vi nào đó. Họ có một số cách thức truyền thông điệp như bấm còi, bật sinh nhan để ra hiệu xin đường, … Chính vì vậy mà việc mô phỏng hệ thống giao thông dựa trên agent là một phương pháp rất thích hợp. 2.2. Mô hình dựa trên agent 2.2.1. Khái niệm về mô hình dựa trên agent – ABM Mô hình dựa trên agent, gọi tắt là ABM ( Agent-Based Modeling ) là một trong các loại mô hình tính toán dùng để mô phỏng các hành động không đồng nhất của các thực thể tự trị trong một môi trường và sự tương tác giữa chúng. Bằng việc mô phỏng lại hoạt động và tương tác giữa các thực thể giống như agent, ABM được sử dụng dể tái tạo hay dự đoán sự hiện diện của những những hiện tượng phức tạp. ABM đặc biệt được dùng để nghiên cứu các hệ thống phức hợp. Trong những hệ thống này, ta sử dụng những nguyên tắc ở mức độ vi mô để tạo ra những hiện tượng mang tính vĩ mô. Những hiện tượng nổi bật này không thể được giải thích bởi một đơn vị vi mô đơn lẻ [2]. Có thể coi ABM là một kỹ thuật mô phỏng mạnh mẽ được sử dụng nhiều năm qua, trong đó có cả các ứng dụng liên quan đến các vấn đề thực tế trong đó có cả thương mại. ABM có một số tên gọi khác nhau như ABS ( Agent-Based Systems ), IBM (Individual-Based Modeling) hay ABMS (Agent-Based Modeling and Simulating) nhưng trong khóa luận này, chúng tôi sẽ sử dụng ABM. 2.2.2. Sự khác nhau giữa agent và đối tượng Từ khi ra đời cho đến nay, công nghệ hướng đối tượng luôn là một phương pháp hữu hiệu trong công nghiệp sản xuất phần mềm. So với phương pháp xây dựng một chương trình theo hướng module như trước, phương pháp hướng đối tượng đã có nhiều ưu điểm vượt bậc. Tuy nhiên, sự ra đời của agent, hệ thống đa agent mà mô hình dựa trên agent đã mở ra một cách thức mới trong xây dựng phần mềm với những ưu việt của nó so với phương pháp hướng đối tượng. Hình 2-1: Ưu việt của agent so với đối tượng Hình 2-1 [3] có thể mô tả được phần nào được sự ưu việt của agent so với đối tượng. Ta có thể thấy rằng, đối tượng chỉ mang tính thụ động do các phương thức của chỉ được thực thi khi các thực thể bên ngoài gửi cho nó một thông điệp nào đó. Trong khi đó, agent có tính chủ động hay tự trị, chúng có thể đưa hành động một cách độc lập mà không chịu sự tác động nào từ bên ngoài. Ngoài ra, giữa chúng còn một số điểm khác biệt như sau [5, 8]: Các phương thức của đối tượng luôn là cố định, không bao giờ thay đổi, trong khi agent có khả năng học hỏi, thích nghi để thay đổi hành vi cho phù hợp với môi trường. Do đó hành vi của đối tượng luôn là có thể đoán trước được, trong khi các hành vi của agent chưa chắc là có thể đoán trước được. Agent có mục tiêu, mục đích, nó có có khả năng lập kế hoạch hay phối hợp với các agent khác để có thể đạt được mục tiêu đó. 2.2.3. Một số ứng dụng của ABM ABM được sử dụng từ những giữa thập kỷ 90 để giải quyết rất nhiều vấn đề về thương mại và công nghệ. Các ví dụ điển hình về ứng dụng của ABM gồm tối ưu dây chuyền cung ứng, mô hình hành vi của người tiêu thụ, các hiệu ứng xã hội, tính toán phân tán, quản lý lực lượng lao động và quản lý hồ sơ. Một số ABM được dùng để phân tích sự lan tràn của dịch bệnh, sự nguy hiểm của vũ khí sinh học, sự phát triển và suy tàn của những nền văn minh cổ đại hay nghiên cứu về sự viêm nhiễm và hệ miễn dịch của con người. Một số ABM được sử dụng để phân tích sự tắc nghẽn của giao thông. Trong những ứng dụng của ABM, hệ thống được quan tâm sẽ được mô phỏng bằng cách tìm ra những hành vi của các agent và mối liên hệ giữa chúng. Các công cụ ABM có thể được sử dụng để kiểm tra xem những thay đổi về hành vi của agent sẽ thay đổi như thế nào đến toàn bộ hệ thống. 2.2.4. Cách xây dựng một ABM Ở mức chung nhất, cách xây dựng một ABM cũng tương tự như cách xây dựng các mô hình khác. Điều cần làm trước tiên là cần xác định được mục đích của mô hình cần xây dựng. Tiếp theo, phân tích nghiên cứu về hệ thống, xác định các thành phần và mối liên hệ giữa chúng. Sau đó, áp dụng mô hình để thực hiện những thí nghiệm nếu-thì đơn giản. Cuối cùng, cần đánh giá được sự hữu dụng của mô hình qua kết quả và việc so sánh nó với các mô hình khác. Sau đây là một số bước cần thực hiện khi xây dựng một ABM [4]: Xác định agent: Xác định loại thực thể của agent, các thuộc tính và các hành vi của chúng Định nghĩa môi trường mà agent sẽ “sống” trong đó Xác định các phương thức mà các thuộc tính của agent được cập nhật trong việc phản ứng lại sự tương tác giữa agent-agent và tương tác agent-môi trường Thêm vào các phương thức điểu khiển việc agent sẽ tương tác với agent nào, khi nào nó tương tác, và nó sẽ tương tác như thế nào trong suốt quá trình mô phỏng Thực thi mô hình 2.3. Kết luận Trên đây, chúng tôi đã trình bầy những khái niệm về cơ bản của agent và hệ thống đa agent cũng như sự ưu việt của nó so với phương pháp hướng đối tượng. Chương này cũng đã nêu ra phương pháp mô phỏng dựa trên trên agent. Đây là một phương pháp pháp tiên tiến trong lĩnh vực mô phỏng những hệ thống phức tạp trong thế giới thực, điều đó thể hiện qua những ứng dụng của nó trong thực tiễn. Ở chương tiếp theo, chúng tôi xin trình bầy về chi tiết về hệ thống mô phỏng giao thông mà chúng tôi đã nghiên cứu và xây dựng. Đây cũng là hệ thống áp dụng mô hình dựa trên agent. CHƯƠNG 3. HỆ THỐNG MÔ PHỎNG GIAO THÔNG VIỆT NAM SỬ DỤNG MÔ HÌNH DỰA TRÊN AGENT 3.1. Một số đặc điểm của giao thông Việt Nam Hệ thống giao thông nước ta, như đã đề cập, là tương đối phức tạp. Sự phức tạp này đến từ nhiều yếu tố khác nhau. Một mặt, cơ sở hạ tầng giao thông nước ta còn chưa phát triển, trong khi lượng phương tiện tham gia giao thông ngày càng tăng với mức độ chóng mặt. Mặt khác, sự thiếu ý thức của người dân khi tham gia giao thông cũng làm cho hệ thống giao thông trở nên hỗn độn. Hệ thống giao thông trước hết gồm các hệ thống đường xá, hệ thống đèn giao thông, và các biển báo. Hầu hết các đường xá ở nước ta nhỏ hẹp, đặc biệt là trong các thành thị. Nhiều ngã ba, ngã tư không có đèn giao thông, hay có đèn giao thông nhưng thời gian bật đèn xanh đèn đỏ chưa hợp lý. Nhiều tuyến đường một chiều, hai chiều có giải phân cách không phù hợp tạo ra những hành vi rẽ trái, rẽ phải hoặc quay đầu không đúng của người tham gia giao thông. Ở nước ta hiện nay có nhiều loại phương tiện giao thông khác như gồm xe đạp, xe máy, ô tô, xe buýt, thậm chí cả các phương tiện không đạt tiêu chuẩn an toàn như xe ba gác, xích lô. Lượng phương tiện tham gia giao thông là rất lớn, trong khi hệ thống đường xá nhỏ hẹp nên thường xảy ra nhiều ách tách, đặc biệt là trong các giờ cao điểm. Một trong những yếu tố quan trọng ảnh hưởng tới giao thông của nước ta chính là yếu tố con người. Do ý thức chưa cao, cộng thêm sự thiếu hiểu biết về các tín hiệu, biển báo, nên sự di chuyển của người tham gia giao thông là rất tùy tiện. Điều đó càng làm tăng tính hỗn độn của giao thông Việt Nam. Từ những đánh giá trên về thực trạng giao thông của nước ta, chúng tôi đã đưa ra những ý tưởng xây hệ thống mô phỏng sao cho dựng phù hợp. Do hệ thống áp dụng mô hình dựa trên agent trong việc mô phỏng nên việc đầu tiên cần làm là xác định các yếu tố môi trường, xác định các agent trong một hệ thống giao thông. Ở phần tiếp theo, chúng tôi xin trình bầy về các ý tưởng về xây dựng hệ thống, gồm hệ thống đường xá – đóng vai trò môi trường và các ý tưởng xây dựng agent đóng vai trò người tham gia giao thông. 3.2. Các ý tưởng xây dựng hệ thống Trước khi đi vào trình bầy chi tiết thiết kế các thành phần của hệ thống mô phỏng, phần này sẽ đưa ra các ý tưởng về cách thức xây dựng hệ thống. Đầu tiên chúng tôi xin đưa ra ý tưởng về xây dựng hệ thống đường xá, đóng vai trò môi trường trong hệ thống giao thông. Tiếp theo sẽ là mô tả chi tiết các ý tưởng về xây dựng agent đóng vai trò người tham gia giao thông. Các ý tưởng xây dựng agent sẽ bao gồm xây dựng các hành vi, các thuộc tính và mục tiêu của agent. Ở cuối phần này, chúng tôi xin đưa ra một số ví dụ minh họa về sự ảnh hưởng của các thuộc tính ảnh lên hành vi của agent trong quá trình di chuyển trong hệ thống giao thông. 3.2.1. Xây dựng hệ thống đường xá Ở chương 1, chúng tôi đã trình bầy về một số hệ thống mô phỏng giao thông trước đây. Đây đều là những hệ thống mô phỏng cho phép tạo ra hệ thống đường từ các thành phần cơ bản. Tuy nhiên, như đã đề cập, hệ thống giao thông Việt Nam khá phức tạp, không theo một quy luật nào. Việc xây dựng hệ thống đường xá của Việt Nam bằng các công cụ mô phỏng này là rất khó khăn. Vì vậy, một thành phần quan trọng cần xây dựng trong hệ thống mô phỏng giao thông Việt Nam chính là hệ thống đường xá. Hệ thống đường xá đóng vai trò môi trường trong hệ thống mô phỏng giao thông sử dụng mô hình dựa trên agent (ABM). Chúng tôi cũng đã cố gắng xây dựng các thành phần cơ bản để tạo nên đường xá. Các thành phần này sẽ giúp tạo ra nhiều mô hình đường xa khác nhau, vì thế mà ta có thể mô phỏng được nhiều hệ thống giao thông phức tạp trong thực tế. Hình 3-1: Chia một ngã tư gồm nhiều tuyến đường thành các vùng đơn giản Với một hệ thống giao thông phức tạp gồm nhiều tuyến đường, ta có thể chia chúng thành các vùng, các đoạn đường nhỏ hơn. Hình 3-1 minh họa việc chia một ngã tư gồm nhiều tuyến đường giao nhau thành các vùng đơn giản hơn. Với các vùng này, ta thấy tám vùng xung quanh chỉ gồm một tuyến đường duy nhất, chỉ có duy nhất vùng ở giữa là chứa nhiều tuyến đường khác nhau từ các hướng đến tới các hướng đi khác nhau. Hình 3-2: Vùng ở giữa ngã tư chứa nhiều tuyến đường khác nhau Dựa vào ý tưởng này, chúng tôi đã xây dựng hệ thống đường xá từ các các thành phần đơn giản là vùng đường và các đoạn đường trong mỗi vùng. Đây có thể coi là thành phân cơ bản nhất của hệ thống đường xá cũng như hệ thống mô phỏng giao thông. Hình 3-3: Các lối vào, lối ra và các đoạn đương trong một vùng Mỗi vùng sẽ có các lối vào và các lối ra. Giữa mỗi lối vào và một lối ra của một vùng đường sẽ có một đoạn đường nào đó. Hướng của đoạn đường là hướng từ lối vào đến lối ra (Hình 3-3). Khi ghép nhiều vùng đường với nhau, các đoạn đường trên các vùng sẽ tạo với nhau thành các tuyến đường. Hình 3-2 mô tả các tuyến đường khác nhau khi ghép vùng ở giữa ngã tư và các vùng chứa đoạn đường thẳng. Các agent đóng vai trò người lái xe trên đường có thể chọn cho mình một tuyến đường đi gồm nhiều đoạn đường nối tiếp nhau, từ vùng này sang vùng kia để có thể đến nơi mà mình muốn đến. Hình 3-4: 16 đoạn đường ở vùng giữa ngã tư Trong ngã tư ở hình 3-3, vùng ở giữa sẽ có 4 lối vào và 4 lối ra, vì vậy số đoạn đường ở vùng giữa ngã tư này là 16 đoạn. Còn với các vùng xung quanh, mỗi vùng chỉ có một lối vào và một lối ra nên chỉ có một đoạn đường trên các vùng này. Hình 3-4 mô tả 16 đoạn đường ở vùng giữa của ngã tư. Cần lưu ý dẫy hình cuối cùng, lối đi quay đầu được tạo từ 2 đoạn đường nối tiếp nhau. Như vậy trong mỗi vùng, các đoạn đường giữa một lối vào và một lối ra không nhất thiết là duy nhất một đoạn đường mà nó có thể là một chuỗi các đoạn đường nối tiếp nhau. Điều này là rất hữu ích vì nó có thể giúp tạo ra các vùng đường tùy ý. Chẳng hạn như ta có thể thiết kế một vùng vòng xuyến bằng cách xấp xỉ đoạn đường cong của vòng xuyến thành các đoạn đường thẳng ngắn nối tiếp nhau. Từ các thành phần cơ bản như vùng đường, các đoạn đường trong mỗi vùng, ta có thể xây dựng đượng nhiều hệ thống giao thông phong phú, đa dạng và phức tạp trong thực tế. Cách thiết kế các thành phần đường xá mà chúng tôi đưa ra không chỉ giúp tạo ra một cách linh động các hệ thống giao thông mà mà còn có tác dụng nâng cao hiệu quả trong việc tính toán cách lái xe của các agent đóng vai trò người tham gia giao thông. Trước khi mô tả tác dụng này ở phần mô tả các thuật toán, chúng tôi xin đưa ra các ý tưởng về xây dựng các agent đóng vai trò người tham gia giao thông ở phần tiếp theo. 3.2.2. Xây dựng agent đóng vai trò người tham gia giao thông Phần trước đã đề cập đến cách thức thiết kế đường xá nhằm tạo ra một hệ thống giao thông bất kỳ. Dù hệ thống giao thông này có phực tạp cỡ nào, ta luôn có thể tìm được một tuyến đường từ một lối vào đến một lối ra khỏi toàn bộ hệ thống giao thông. Ở đây, ta giả thiết các agent khi bắt đầu tại một đầu vào sẽ có mục tiêu là sẽ đi đến một đầu ra nào đó của hệ thống và mục tiêu này là không đổi trong suốt quá trình di chuyển của agent. Giả sử trên một hệ thống giao thông được tạo ra chỉ có một agent đang di chuyển, thì việc di chuyển của agent hết sức đơn giản. Agent đó chỉ cần di chuyển theo một tuyến đường định trước, đi hết đoạn đường này sang đoạn đường khác hay từ vùng đường này sang vùng đường khác rồi kết thúc di chuyển khi đến đích. Nhưng khi có nhiều agent trên hệ thống này, ngoài việc tuân thủ các luật lệ của môi trường ở đây là hệ thống đường xá, các agent cần chú ý đến các agent khác khi di chuyển. Tùy từng tình huống, và cũng tùy vào các agent khác nhau mà cách di chuyển của nó sẽ khác nhau. Trong phần này, chúng tôi xin trình bầy về các hành vi và các thuộc tính của mỗi agent. 3.2.2.1. Các hành vi cơ bản của mỗi agent Để di chuyển, các agent cần có các hành động hợp lý tùy từng tình huống. Mỗi hành động này các agent sẽ đảm bảo một số yêu cầu là: Hướng đến đích, không va chạm với lề đường và không va chạm với các agent khác. Chúng tôi xin đưa ra các hành động cơ bản nhất của mỗi agent bao gồm: Tăng tốc Giảm tốc Đánh lái hay hành động điều chỉnh hướng xe Các agent sẽ thực hiện tăng tốc khi vận tốc hiện tại đang thấp hoặc đang ở trạng thái dừng và phải đảm bảo ở phía trước không có agent nào. Việc giảm tốc sẽ được thực hiện khi các agent nhận thấy nếu duy trì ở vận tốc hiện tại thì sẽ gây ra va chạm với agent khác hoặc va chạm với lề đường, ... Để điều chính xe theo đúng hướng đi của đường hoặc cần điều chỉnh hướng đi để tránh các agent khác, mỗi agent đều cần phải có hành động là đánh lái. 3.2.2.2. Xây dựng các thuộc tính đăng trưng cho mỗi agent Tùy từng tình huống khác nhau mà các agent sẽ đưa ra các hành động khác nhau. Tuy nhiên, kể cả khi gặp một cùng tình huống, những agent khác nhau khác nhau cũng sẽ chọn các cách hành động khác nhau. Sự khác nhau này được tạo ra bởi sự khác nhau về thuộc tính của các agent. Đối với những người tham gia giao thông thì tuổi tác, giới tính, tính cách, kinh nghiệm, … sẽ chi phối đến cách lái xe của từng người. Dựa vào những nhận xét trên, chúng tôi đã xây dựng các thuộc tính mang tính đặc trưng cho mỗi agent. Giá trị của các thuộc tính này sẽ phụ thuộc vào tuổi tác và giới tính của từng người. Theo hệ quả, giá trị của các thuộc tính này sẽ ảnh hưởng đến lựa chọn hành động lái xe của từng agent đóng vai trò người tham gia giao thông. Các thuộc tính đó gồm: Tốc độ tối đa Mức độ tăng tốc Tốc độ an toàn Khoảng thời gian dự tính Tốc độ tối đa là tốc độ lớn nhất mà agent có thể đạt được cho dù di chuyển trên bất cứ đoạn đường nào, dù có hay không có agent phía trước. Các lứa tuổi và giới tính khác nhau sẽ có tốc độ khác nhau, chẳng hạn như tốc độ tối đa của nam giới thường cao hơn nữ giới. Giá trị của thuộc tính này sẽ ảnh hưởng đến sự lưu thông trên đường. Mức độ tăng tốc chỉ khả năng tăng tốc của agent. Các agent sẽ thực hiện hành động tăng tốc khi đang ở tốc độ thấp hoặc đang ở trạng thái dừng trong khi phía trước không có xe nào. Cũng như tốc độ tối đa, mức độ tăng tốc của các agent khác nhau là khác nhau. Mức độ tăng tốc của thanh niên thường cao hơn người già, của nam giới thường cao hơn nữ giới. Mức độ tăng tốc của các agent rất có ảnh hưởng đến sự lưu thông trên đường. Chẳng hạn như tại các đoạn ùn tắc, các xe khi thoát khỏi đám đông mà tăng tốc càng nhanh sẽ càng tạo khoảng trống cho các xe phía sau nhanh hơn. Tốc độ an toàn là giá trị có liên quan mật thiết đến lựa chọn đánh lái của các agent. Khi cần đánh lái, các agent cần giảm tốc độ xuống tốc độ an toàn. Ví dụ, khi một người đang đi xe với một vận tốc nào đó mà nhận thấy sẽ va chạm vào xe khác phía trước nếu duy trì hướng và vận tốc hiện tại. Nếu vận tốc hiện tại lớn hơn vận tốc an toàn thì người này nhất thiết phải giảm tốc độ, nếu không thì người đó có thể xem xét việc đánh lái để tránh xe phía trước. Giá trị của tốc độ an toàn sẽ phụ thuộc vào giới tính và tuổi tác người lái. Ở người già, giá trị này thường thấp, còn ở người trung niên và thanh niên thì giá trị này cao hơn. Khoảng thời gian dự tính là quãng thời gian sắp tới mà mỗi agent cần xác định cách lái xe tốt nhất cho mình. Giá trị của thuộc tính này thường nhỏ, từ vài trăm miligiây đến vài giây, tùy thuộc từng lứa tuổi, giới tính. Giá trị này có ảnh hưởng đến cách lựa chọn hành động của các agent. Giả sử một agent đang chuyển động với vận tốc 30km/h và giá trị của thuộc tính này là 600 miligiây thì agent này cần xác định được cách lái tốt nhất trong quãng đường 4.98m sắp tới. Giá trị này ở các lứa tuổi khác nhau sẽ khác nhau. Giá trị này ở người trung tuổi và người già sẽ cao hơn thanh niên. Thuộc tính tốc độ an toàn thể hiện tính cẩn thận của các người lái, trong khi thuộc tính khoảng thời gian dự tính thể hiện sự “nhìn xa trông rộng” của các người lái. 3.2.2.3. Các ví dụ về sự ảnh hưởng của các thuộc tính lên cách lựa chọn hành động của agent Ví dụ 1: Các giá trị khác nhau của tốc độ an toàn ảnh hưởng đến cách lái xe khác nhau. Hình 3-5 minh họa hai agent đóng vai trò một thanh niên và một người già tham gia giao thông gặp tình huống giống nhau nhưng sẽ cho quyết định khác nhau. Cả hai agent này đều đang di chuyển với vận tốc là 26km/h và sẽ va chạm với xe trước mặt trong khoảng 1000 miligiây tới nếu tiếp tục đi thẳng và duy trì vận tốc hiện thời. Tuy nhiên, do giá trị vận tốc an toàn của agent giữ vai trò người thanh niên là 30km/h cao hơn vận tốc hiện thời, nên agent này đã xem xét trường hợp đánh lái. Vì xét thấy đánh lái sang trái là an toàn vì không chạm lề đường hay agent nào khác nên agent thanh niên đã chọn quyết định đánh lái sang trái. Còn agent người già do đang di chuyển với vận tốc 26km/h, cao hơn vận tốc an toàn là 20km/h nên đã chọn luôn quyết định giảm tốc độ mà không xem xét các lựa chọn nào khác. (a) Thanh niên Vận tốc hiện thời: 26km/h Vận tốc an toàn: 30km/h Thời gian dự tính: 1000ms Lựa chọn: Đánh lái sang trái (b) Người già Vận tốc hiện thời: 26km/h Vận tốc an toàn: 20km/h Thời gian dự tính: 1000ms Lựa chọn: Giảm tốc Mũi tên mầu xám chỉ ra người già không hề xem xét lựa chọn đánh lái sang trái Hình 3-5: Thuộc tính vận tốc an toàn ảnh hưởng đến cách lái xe của các agent Ví dụ 2: Các agent có khoảng thời gian dự tính khác nhau sẽ có cách lái xe khác nhau. Hình 3-6 mô tả hai agent đóng vai trò một người trung tuổi và một thanh niên gặp một tình huống giống hệt nhau khi tham gia giao thông. Cả hai đều đang di chuyển với vận tốc là 26km/h, nhỏ hơn vận tốc an toàn, do đó có thể xem xét các lựa chọn tránh xe nếu xét thấy sẽ va chạm với agent khác phía trước. Tuy nhiên, do khoảng thời gian dự tính của agent người trung tuổi là cao hơn do đó quãng đường phải xem xét va chạm với các xe khác là dài hơn. Trong trường hợp này, agent người trung tuổi đã xem xét cả 3 lựa chọn và đều thấy sẽ va chạm với các agent nên đành đưa ra quyết định giảm tốc. Với agent thanh niên, do quãng đường dự tính là ngắn hơn nên đã cho rằng sẽ không xảy ra va chạm với agent phía trước bên phải nên đã chọn cách đánh lái đi về phía bên phải. (a) Người trung tuổi Vận tốc hiện thời: 26km/h Vận tốc an toàn: 28km/h Thời gian dự tính: 1200ms Lựa chọn: Giảm tốc (b) Thanh niên Vận tốc hiện thời: 26km/h Vận tốc an toàn: 30km/h Thời gian dự tính: 1000ms Lựa chọn: Đánh lái sang phải Hình 3-6: Thuộc tính thời gian dự tính ảnh hưởng đến cách lái xe của các agent 3.3. Mô tả hệ thống Từ những ý tưởng đã trình bầy ở trên, chúng tôi đã thiết kế hệ thống dựa trên các ý tưởng này. Phần này sẽ đi vào mô tả thiết kế hệ thống bao gồm các thành phần dữ liệu và các thuật toán được sử dụng cho việc mô phỏng. 3.3.1. Các thành phần chính của hệ thống Phần này xin trình bầy các thành phần chính của hệ thống, chủ yếu phục vụ cho công việc mô phỏng. Các thành phân này được thiết kế theo hướng đối tượng, nên sẽ được mô tả dưới dạng lớp. Biểu đồ UML sau sẽ mô tả các các thuộc tính, các phương thức của các lớp và mối quan hệ giữa chúng. Hình 3-7: Biểu đồ mô tả các thành phần của hệ thống và mối quan hệ của chúng Dưới đây là mô tả chi tiết các thuộc tính và các phương thức của từng lớp: Lớp Gate Đây là lớp dùng để mô tả một lối vào và một lối ra, gọi chung là cổng. Mỗi cổng được chỉ ra bởi hai điểm là leftPoint – điểm bên trái và rightPoint – điểm bên phải. Thuộc tính area dùng để lưu vùng đường mà cổng này liên thông tới. Lớp Area Đây là lớp mô tả vùng đường đã được nêu ra ở mục 3.2.1. Các thuộc tính của lớp này gồm có: entries: Danh sách các lối vào exits: Danh sách các lối ra roads: Danh sách các đoạn đường giữa các lối vào và các lối ra vehicles: Danh sách các xe (agent) đang di chuyển trong vùng. Như đã đề cập, việc phân chia hệ thống đường xá không chỉ nhằm mục đích tạo ra các hệ thống đường tùy ý, mà còn giúp nâng cao hiệu quả xử lý tránh xe của các agent. Khi di chuyển trong một vùng, các agent chỉ cần quan tâm đến các agent ở vùng hiện thời và một số vùng liên quan chứ không cần xem xét mọi agent trong toàn bộ hệ thống giao thông. Danh sách này phục vụ cho mục đích đó và nó giúp nâng cao hiệu quả xử lý tránh xe đáng kể. Chẳng hạn có khoảng vài nghìn agent trong hệ thống giao, nhưng khi xử lý việc di chuyển, mỗi agent chỉ xem cần xem xét va chạm với vài chục agent khác mà vẫn có thể di chuyển một cách hợp lý. Các phương thức quan trọng của lớp Area gồm: getVihicles():Vehicle[]: Trả lại danh sách các xe di chuyển trong vùng. connectArea(area:Area): Giúp kết nối 2 vùng với nhau. Việc kết nối sẽ dựa vào thông tin các lối vào và các lối ra giữa của 2 vùng. Kết nối sẽ được thực hiện chỉ khi tọa độ của lối vào của vùng này khớp với tọa độ lối ra của vùng kia hoặc ngược lại. route(): Phương thức sẽ tìm và này trả về đoạn đường đầu tiên của tuyến đường đi từ lối vào của một vùng đến lối ra của một vùng khác. Phương thức này giúp xác định các tuyến đường giữa các lối vào và các lối ra của hệ thống giao thông. Lớp Road Lớp này mô tả một đoạn đường như trong mô tả ở mục 3.2.1. Mối đoạn đường đơn giản được mô tả bởi 2 đoạn thẳng đóng vai trò lề ở hai bên đường. Ngoài ra nó có thêm một số thông tin khác để phục vụ cho việc tính toán di chuyển của các agent. Các thuộc tính của lớp này gồm: leftPave: Đoạn thẳng mô tả bởi 2 điểm, chỉ ra lề bên trái của đoạn đường. rightPave: Cũng như vậy, đây là đoạn thẳng chỉ ra lề bên phải của đoạn đường. next: Đây là đoạn đường tiếp theo đoạn đường hiện thời. Một tuyến đường sẽ gồm một dẫy nối tiếp nhau của các đoạn đường. Nhờ thuộc tính này, một tuyến đường sẽ xác định khi biết được đoạn đường đầu tiên của tuyến đường. direction: Vector chỉ hướng đi của đường. Thuộc tính này sẽ định hướng cho các agent khi di chuyển. area: Khu vực chứa đoạn đường. Mỗi đoạn đường đều phải nằm trong một vùng đường nào đó. Thuộc tính này giúp các agent biết chúng đang di chuyển trên vùng nào. Các phương thức quan trọng của lớp Road gồm: getDirection():Vector: Trả lại vector chỉ hướng của đường. getDistanceToLeftPave(p:Point): Trả lại khoảng cách từ một điểm đến lề trái. getDistanceToRightPave(p:Point): Trả lại khoảng cách từ một điểm đến lề phải. getDistanceToEnd(p:Point): Trả lại khoảng cách từ một điểm đến vạch cuối của đoạn đường. getNext():Road: Trả lại đoạn đường tiếp theo. getArea():Area: Trả lại vùng chứa đoạn đường. Các phương thức này đều phục vụ cho xử lý sự di chuyển của các agent. Lớp DriverAttributes Lớp này mô tả các thuộc tính đặc trưng của người lái, đây chính là các thuộc tính mà chúng tôi đã trình bầy trong phần ý tưởng về xây dựng agent đóng vai trò người tham gia giao thông (phần 3.2.2.2). Các thuộc tính của lớp này gồm: gender: Chỉ ra giới tính của agent. Thuộc tính này sẽ tác động đến giá trị của một số thuộc tính khác mô tả bên dưới age: Tuổi tác của agent. Cũng như vây, thuộc tính này sẽ có ảnh hưởng tới một số thuộc tính mang tính đặc trưng của mỗi agent. maxSpeed: Tốc độ tối đa của agent. Giá trị này sẽ khác nhau với các giá trị khác nhau của thuộc tính gender và age. incSpeed: Mức độ tăng tốc của agent. Giá trị này thường cao ở nam giới và thanh niên. safeSpeed: Tốc độ an toàn chỉ ra tốc độ cần giảm xuống trước khi thực hiện việc đánh lái để tránh xe. Agent sẽ không bao giờ đánh lái để tránh xe nếu tốc độ hiện thời cao hơn tốc độ an toàn. planTime: Tại mỗi thời điểm, mỗi agent cần xây dựng đượng chiến thuật lái xe tốt nhất cho mình trong khoảng thời gian planTime sắp tới. Lớp Vehicle Đây chính là lớp mô tả agent đóng vai trò người tham gia giao thông. Các thuộc tính của lớp này gồm: position: Vị trí hiện tại của agent. road: Đoạn đường hiện tại mà agent đang di chuyển velocity: Vector vận tốc của agent, bao gồm cả hướng và độ lớn của vận tốc. length, width: Mỗi xe được coi như một hình chữ nhât. Giá trị của hai thuộc tính này chỉ ra chỉ chiều dài, và chiều rộng của hình chữ nhật đó. attributes: Các thuộc tính đặc trưng của người lái Các phương thức của lớp này chủ yếu phục vụ cho việc tính toán di chuyển của agent, chúng bao gồm: distance(vehicle:Vehicle):float: Tính toán và trả về khoảng cách giữa 2 agent. Khoảng cách giữa 2 agent sẽ phụ thuộc vào vị trí, hướng và kích thước của mỗi agent. updatePosition(): Cập nhật vị trí hiện tại của agent. Vị trí mới của agent sẽ phụ thuộc vào vector vận tốc. Sau khi thay đổi vị trí, agent cần xác định đoạn đường mà nó đang đứng ở vị trí mới. Nếu là đoạn đường khác với đoạn đường vị trí cũ và đoạn đường mới này cũng nằm ở vùng đường mới, khác với vùng đường cũ, thì cần cập nhật danh sách các agent đang di chuyển trong các vùng. checkAvoidChoice(): Đây là phương thức kiểm tra lựa chọn đánh lái để tránh xe. Phương thức này được gọi từ trong phương thức drive() mô tả bên dưới và nó chỉ được gọi khi vận tốc hiện thời nhỏ hơn vận tốc an toàn (safeSpeed). drive(): Đây là phương thức thực hiện toàn bộ việc tính toán di chuyển của agent. Nó thể hiện được các tính chất của agent. Phương thức này sẽ được mô tả chi tiết trong phần mô tả các giải thuật tiếp theo. Các giải thuật được cài đặt trong các phương thức checkAvoidChoice() và phương thức drive() sẽ được chúng tôi mô tả chi tiết trong phần tiếp theo. 3.3.2. Các thuật toán được sử dụng Trong phần này, chúng tôi sẽ trình bầy chi tiết về thuật toán thuật được sử dụng để điều khiển sự di chuyển của các agent. Đây là một thuật toán sử dụng một số các thuật toán khác đơn giản hơn. Hình 3-8: Thuật toán tính toán di chuyển của agent Hình 3-8 là biểu đồ của thuật toán tính toán sự di chuyển của agent. Thuật toán này được cài đặt trong phương thức drive() của lớp Vehicle. Trong các thuật toán được sử dụng bên trong phương thức này, thì các thuật toán quan trọng nhất bao gồm: Thuật toán xây dựng kế hoạch lái xe lý tưởng của agent Thuật toán kiểm tra va chạm với agent khác nếu đi theo một kế hoạch lý tưởng Thuật toán kiểm tra lựa chọn tránh xe khi có agent khác đang di chuyển phía trước Sau đây chúng tôi xin đi vào trình bầy chi tiết từng thuật toán này. 3.3.2.1. Xây dựng kế hoạch lái xe lý tưởng Đây là bước đầu tiên cần thực hiện trong giải thuật tính toán sự di chuyển của các agent và nó thể hiện được khả năng lập kế hoạch của các agent tham gia giao thông. Ở đây, kế hoạch lái xe lý tưởng là kế hoạch lái xe của agent nhằm đi đến đích trong thời gian ngắn nhất, nhưng đây là kế hoạch lái xe khi agent coi như không có bất cứ agent nào khác trên đường (vì thế nó được gọi là lý tưởng). Đây thực chất là một vòng lặp lần lượt xác định các vị trí tiếp theo của xe trên đường. Ở mỗi lần lặp, agent sẽ “tưởng tượng” vị trí tiếp theo của mình bằng cách lấy tọa độ hiện tại dịch lên phía trước một khoảng nào đó. Độ dài mỗi lần dịch chuyển sẽ được xác định tùy thuộc vào vận tốc hiện tại, nhưng luôn phải nhỏ hơn chiều dài của xe để đảm bảo việc tính toán va chạm với agent khác một cách chính xác (thực hiện ở thuật toán (2)). Hình 3-9: Agent lập kế hoạch lý tưởng trên đường dài và thẳng Hình 3-9 minh họa một agent lập một kế hoạch lái xe lý tưởng trên đường thẳng dài. Nếu không có agent nào khác, agent cứ đi theo kế hoạch này sẽ đến đích nhanh nhất. Hình ảnh này cho ta thấy mối liên hệ giữa số lần dịch chuyển và thuộc tính planTime của agent. Hay nói đúng hơn planTime sẽ xác định số lần dịch chuyển trong kế hoạch. Gọi ∆l là độ dài mỗi lần dịch chuyển, do đó thời gian mỗi lần dịch chuyển là: ∆t = ∆l/v Với v là vận tốc hiện thời của xe, khi đó số lần dịch chuyển (số lần lặp) sẽ là: n = [planTime/∆t] Với đoạn đường thẳng dài như hình 3-9, hướng dịch chuyển cho mỗi lần dịch chuyển luôn trung với hướng đường. Tuy nhiên, với hệ thống đường phức tạp, có nhiều lối rẽ, nhiều đoạn đường đổi hướng, ta cần phải có cách xác định được hướng dịch chuyển nào đó. Ta thấy ở mỗi thời điểm dịch chuyển, agent có 3 lựa chọn là: tiếp tục dịch chuyển thẳng về phía trước, dịch chuyển về phía trái, dịch chuyển về phía phải. Trong 3 hướng này, ta chỉ cần chọn hướng làm cho độ dài còn lại trên toàn bộ tuyến đường là ngắn nhất. Hình 3-10: Thuật toán xây dựng kế hoạch di chuyển lý tưởng của agent Từ những cơ sở tính toán ở trên, chúng tôi xin đưa ra biểu đồ mô tả thuật toán xây dựng lế hoạch di chuyển lý tưởng của agent trên hệ thống đường bất kỳ trong hình 3-10. Hình 3-11: Agent lập kế hoạch di chuyển lý tưởng trên hệ thống đường bất kỳ Hình 3-11 mô tả một agent lập kế hoạch lý tưởng trên một đoạn đường bất kỳ. Vận tốc hiện thời của agent là 30km/h và thời gian của kế hoạch dự tính là 600ms tức là độ dài của quảng đường dự tính là 5m. Khoảng cách dịch chuyển mỗi lần là 1m, nên kế hoạch sẽ được xây dựng qua 5 lần dịch chuyển. Các điểm ở đầu mút ở mỗi mũi tên in đậm chính là các điểm mà agent sẽ hướng tới để thực hiện việc di chuyển lý tưởng. Agent sẽ di chuyển theo kế hoạch lý tưởng nếu nhận thấy không va chạm với bất cứ agent nào khác. Nhưng nếu nhận thấy sẽ va chạm với agent khác, agent sẽ xem xét việc tránh va chạm hoặc giảm tốc nếu bắt buộc. Thuật toán kiểm tra va chạm với các agent khác nếu di chuyển theo kế hoạch lý tưởng sẽ được mô tả ở mục tiếp theo. 3.3.2.2. Kiểm tra va chạm với agent khác nếu di chuyển theo kế hoạch lý tưởng Bược tiếp theo trong thuật toán tính toán sự di chuyển của agent là kiểm tra va chạm với các agent khác nếu đi theo hành trình lý tưởng đã định ra. Trong một môi trường có nhiều agent, mỗi agent đều có cảm nhận về các agent xung quanh trong một phạm vi nào đó. Trong hệ thống giao thông, mỗi agent đóng vai trò người tham gia giao thông đều có thông tin các agent đang di chuyển ở phía trước và ở hai bên trong một phạm vi giới hạn. Các thông tin này bao gồm vị trí, hướng, và tốc độ của các agent. Nhờ thông tin này mà agent có thể cảm nhận được sẽ va chạm với agent khác hay không khi đi theo một hành trình nào đó. Hình 3-12: Agent cảm nhận được va chạm với agent khác Hình 3-12 minh họa một agent cảm nhận được sự va chạm với agent khác nếu đi theo lộ trình của kế hoạch lý tưởng. Nhờ nhận biết được vị trí, hướng, và tốc độ hiện thời của agent B, agent A sẽ cảm nhận được các vị trí tiếp theo của agent B ở mỗi lần dịch chuyển. Nhờ đó agent A có thể dự tính được khoảng cách giữa nó và agent B ở các thời điểm này và nếu khoảng cách ấy là đủ nhỏ, nó có thể kết luận va chạm có thể sẽ xảy ra. Ở hình 3-13, agent A nhận thấy trong các thời điểm khi dịch chuyển đến vị trí thứ nhất, thứ hai và thứ ba trên lộ trình của kế hoạch lý tưởng, nó sẽ không va chạm với bất cứ agent nào. Nhưng ở thời điểm khi dịch chuyển đến vị trí thứ tư, agent A đã cảm nhận được sẽ xảy ra va chạm với agent B. Do đó, agent A cần hủy bỏ việc đi theo lộ trình này và phải xem xét các lựa chọn khác. Hình 3-13: Agent hình dung vị trí của agent khác ở các thời điểm dịch chuyển Từ những nhận xét trên, chúng tôi xin đưa ra biểu đồ mô tả thuật toán kiểm tra va chạm của agent với các agent khác nếu thực hiện kế hoạch di chuyển lý tưởng. Hình 3-14: Thuật toán kiểm tra va chạm nếu di theo chuyển theo kế hoạch lý tưởng Sau khi kiểm tra, nếu nhận thấy sẽ không va chạm với agent nào, agent sẽ đi theo kế hoạch lý tưởng. Nhưng nếu cho rằng va chạm sẽ xảy ra, agent có một trong các lựa chọn là giảm tốc độ hoặc đánh lái để tránh va chạm. Nếu tốc độ hiện thời của agent cao hơn tốc độ an toàn, thì giảm tốc là bắt buộc. Nếu không, agent có thể xem xét việc đánh lái. Việc xem xét đánh lái để tránh va chạm sẽ được thực hiện ở giải thuật mô tả ở mục tiếp theo. 3.3.2.3. Kiểm tra các trường hợp đánh lái để tránh va chạm Đây chính là giải thuật được cài đặt trong phương thức checkAvoidChoice() của lớp Vehicle và sẽ được thực hiện chỉ khi tốc độ hiện tại của agent thấp hơn tốc độ an toàn (safeSpeed). Thuật toán này thực chất chỉ kiểm tra va chạm của agent với các agent khác khi đi theo các lộ trình song song với lộ trình của kế hoạch lý tưởng. Đầu tiên agent sẽ xem xét các hướng có thể đánh lái. Tiếp theo, nó sẽ thực hiện kiểm tra va chạm khi đi trên lộ trình song với lộ trình của kế hoạch lý tưởng. Agent trong hình 3-15 chỉ có thể xem xét việc đánh lái sang bên trái rồi thực hiện kiểm tra va chạm trên lộ trình song song với lộ trình của kế hoạch lý tưởng. Kết thúc quá trình kiểm tra, agent này nhận thấy sẽ không va chạm với agent nào nên quyết định đánh lái về phía bên trái. Hình 3-15: Agent kiểm tra lựa chọn đánh lái để tránh va chạm Thuật toán này tương tự như thuật toán kiểm tra va chạm khi đi theo kế hoạch lý tưởng. Đó là cứ mỗi lần dịch chuyển, agent sẽ tính toán vị trí tương ứng của các agent khác. Nếu nhận thấy có agent nào tiến đến đủ gần vị trí dịch chuyển, nó sẽ kết luận va chạm sẽ xảy ra. Trên đây, chúng tôi đã trình bầy toàn bộ về thiết kế của hệ thống gồm các thành phần vùng đường, đoạn đường, xe cộ và mối liên hệ giữa chúng cùng với các giải thuật được sử dụng. Ở phần tiếp theo, chúng tôi xin mô tả sơ lược về việc cài đặt hệ thống dựa vào những thiết kế này. 3.4. Cài đặt hệ thống mô phỏng Từ những thiết kế về các thành phần của hệ thống và các giải thuật được sử dụng, chúng tôi đã cài đặt hệ thống bằng ngôn ngữ C++. Để tiện lợi trong việc phát triển và mở rộng, chúng tôi đã chia phần cài đặt của hệ thống thành các gói có các chức năng riêng biệt bao gồm: Gói sim: Chứa các module cài đặt các lớp của hệ thống mô phỏng giao thông bao gồm cả đường xá lẫn xe cộ. Gói renderer: Chứa các module cài đặt chức năng hiển thị toàn bộ hệ thống mô phỏng. Gói util: Chứa các module hỗ trợ. Gói builtin: Chứa các module cài đặt các loại đường dựng sẵn. Gói program: Chứa các module cài đặt chương trình chạy. Gói sim Gói này chứa các module cài đặt các lớp của hệ thống mô phỏng giao thông. Gói này gồm rất nhiều lớp phục vụ cho việc mô phỏng giao thông, trong đó có các lớp quan trọng sau: Lớp Gate: Gồm gate.h và gate.cpp, chứa phần mô tả và cài đặt các lối vào, lối ra trong các vùng đường. Lớp Road: Gồm road.h và road.cpp,mô tả và cài đặt của thành phần đoạn đường. Lớp Area: Gồm area.h và area.cpp, mô tả và cài đặt thành phần vùng đường. Lớp DriverAttributes: Gồm Driver.h và Driver.cpp, mô tả và cài đặt các thuộc tính và phương thức liên quan đến đặc tính của agent tham gia giao thông. Lớp Vehicle: Gồm vehicle.h và vehicle.cpp chứa phần mô tả và cài đặt của xe cộ, chính là agent đóng vai trò người tham gia giao thông. Lớp TrafficSimulator: Gồm trafficsimulator.h, trafficsimulator.cpp và trafficsimulator_win32.cpp, chứa phần mô tả và cài đặt của toàn bộ hệ thống mô phỏng. Tệp trafficsimulator_win32.cpp chứa phần cài đặt của các phương thức phụ thuộc vào hệ điều hành Windows, chẳng hạn như thread. Gói renderer Gói này chứa các module cài đặt cho việc hiển thị toàn bộ hệ thống mô phỏng bao gồm hiển thị đường xá, hiển thị các xe đang đi lại và hiển thị một số thông tin khác. Chúng tôi đã sử dụng thư viện OpenGL để cài đặt các công việc hiển thị này. Lớp quan trọng của gói này gồm có AreaRenderer và Renderer lần lượt thực hiện việc hiển thị một vùng đường nào đó và hiển thị toàn bộ hệ thống đường xá cùng các xe đi lại. Gói util Gói này chứa phần cài đặt các lớp hỗ trợ bao gồm: Point2D: Gồm point2d.h và point2d.cpp chứa phần mô tả một điểm trong không gian 2 chiều và phần cài đặt các phép toán với điểm như tịnh tiến, quay,… Vector2D: Gồm vector2d.h và vector2d.cpp chứa phần mô tả một vector 2 chiều và phần cài đặt các phép toán như tích vô hướng, tính góc giữa 2 vector, … Gói builtin Gói này chứa một số loại vùng đường dựng sẵn như các đoạn đường thẳng, các đoạn đường có lối rẽ, ngã tư, ngã tư có vòng xuyến,.... Ta có thể ghép các vùng đường này với nhau để tạo ra nhiều hệ thống giao thông đa dạng, phức tạp như trên thực tế. Gói program Chứa các module cài đặt chương trình mô phỏng, bao gồm các tệp tin VTSMain.h, VTSMain.cpp và VTSMain_win32.cpp chứa các khai báo và thực thi các thành phần chính của chương trình. Tệp VTSMain_win32.cpp chứa các thủ tục thực thi chương trình chạy trên nền Windows. 3.5. Giới thiệu chương trình mô phỏng Chương trình được chúng tôi lập trình để chạy trên hệ điều hành Windows. Chương trình rất dễ sử dụng do sử dụng Tiếng Việt và có thể chạy trực tiếp, không cần cài đặt. Chương trình có hai chế độ gồm chế độ thiết kế và chế độ mô phỏng. Chế độ thiết kế cho phép người sử dụng thiết kế các hệ thống đường xá và chế độ mô phỏng cho phép người sử dụng quan sát sự di chuyển các xe trên hệ thống đường xá mà họ đã thiết kế, đồng thời cung cấp một số thông tin thống kê như số xe qua lại, thời gian di chuyển trung bình của các xe, ..vv. 3.5.1. Chế độ thiết kế Hình 3-16 mô tả giao diện chương trình trong chế độ thiết kế. Bảng bên trái chứa một số tùy chọn và công cụ hỗ trợ cho việc thiết kế. Vùng bên phải là vùng hiển thị hệ thống các thành phần của hệ thống đường xá. Người sử dụng có thể di chuyển, phóng to và thu nhỏ khung nhìn. Khung nhìn được vẽ với ô lưới nhằm giúp người sử dụng dễ dàng hình dung các kích thước (thông tin về kích thước của ô lưới nằm phía dưới bên trái). Khi người sử dụng ấn chuột vào một đường nào đó, đường đó sẽ được coi là được chọn. Người sử dụng có thể di chuyển đường được chọn bằng chuột. Để quay đường được chọn, người dùng sử dụng cần ấn nút . Hình 3-16: Giao diện chương trình ở chế độ thiết kế Mỗi đường thực chất là một Vùng đường mà chúng tôi đã mô tả trong thiết kế của hệ thống. Các lối vào và các lối ra của đường sẽ được thể hiện bằng các đoạn thẳng màu xanh và màu đỏ tương ứng. Các đường có thể được sắp xếp và và ghép lại với nhau một cách tùy ý. Một lối vào của một vùng đường sẽ ghép được với bất cứ lối ra nào của một vùng khác nếu chúng “khớp” nhau. Hình 3-17 minh họa việc ghép hai vùng đường với nhau, sự biến mất của các đoạn thẳng màu xanh và màu đỏ chỗ “mối ghép” thể hiện việc ghép nối đã thành công. Hình 3-17: Ghép các vùng đường với nhau để tạo thành hệ thống đường xá tùy ý Chương trình cung cấp một số thành phần đường cơ bản dựng sẵn nhằm giúp người sử dụng có thể thiết kế các hệ thống giao thông phức tạp một cách dễ dàng. Để có thể thêm các thành phần đường này vào cửa sổ hiển thị, người dùng cần ấn nút để mở một hộp thoại lựa chọn các thành phần đường cần thêm. Hình 3-18: Hộp thoại chọn các thành phần đường dựng sẵn Hình 3-18 mô tả hộp thoại chứa danh sách các thành phần đường dựng sẵn. Cửa sổ bên phải hiển thị hình dạng của đường và các kích thước của đường. Người sử dụng có thể ấn chuột vào các con số để điều chỉnh theo ý muốn. Từ các thành phần có sẵn này, người dùng có thể thiết kế được nhiều hệ thống đường xá phong phú giống với thực tế. Sau khi hoàn thành công việc thiết kế, người sử dụng có thể tùy chọn số người tham gia giao thông bằng cách ấn vào nút để mở một hộp thoại tùy chọn. Có ba lứa tuổi tham gia giao thông là thanh niên, người trung tuổi và người già. Còn với giới tính, chương trình được cài đặt mặc định là số nam và số nữ giới bằng nhau. Hình 3-19: Hộp thoại tùy chọn số người tham gia giao thông Ngoài tùy chọn về số người tham gia giao thông, người dùng còn có thể thiết đặt các thuộc tính của người tham gia giao thông bằng cách ấn vào nút . Đây có thể coi là chức năng làm tăng sự linh động của chương trình. Hình 3-20: Hộp thoại tùy chọn các thuộc tính của người lái Sau khi hoàn tất tất cả các công việc thiết kế và tùy chọn, người sử dụng cần ấn vào nút để thực hiện quá trình mô phỏng. 3.5.2. Chế độ mô phỏng Khi chương trình chạy ở chế độ mô phỏng, vùng cửa sổ bên phải sẽ hiển thị các hệ thống đường đã được thiết kế cùng các xe di chuyển trên hệ thống đường này. Các xe sẽ bắt đầu di chuyển tại một lối vào của hệ thống đường xá và sẽ kết thúc chuyến đi của mình ở một lối ra nào đó. Trong quá trình di chuyển đến đích, các xe cần phải tránh các xe khác và không được va vào lề đường. Hình 3-21: Giao diện chương trình ở chế độ mô phỏng Bảng bên trái cung cấp một số chức năng điều khiển như điều chỉnh tốc độ, tạm dừng và hiển thị các thông tin thống kê. Bên cạnh việc quan sát sự di chuyển của các xe, nhờ các thông tin thống kê mà người sử dụng có thể có một cái nhìn trực quan hơn về quá trình mô phỏng. Các thông tin thống kê quan trọng bao gồm: Thời gian: Quãng thời gian đã trôi qua của quá trình mô phỏng Số xe về đích: Là lượng xe đã kết thúc chuyến đi từ một lối vào đến lối ra hệ thống Thời gian đi trung bình: Thời gian di chuyển trung bình của tất cả các xe đã về đích Trên đây, chúng tôi đã giới thiệu sơ lược về chương trình mô phỏng giao thông mà chúng tôi đã xây dựng. Ở phần tiếp theo, chúng tôi sẽ trình bầy một số thử nghiệm nhằm đưa ra một số đánh giá về chương trình mô phỏng này. 3.6. Một số thử nghiệm và nhận xét Để thử nghiệm, chúng tôi sẽ thực hiện một số quá trình mô phỏng và lấy một kết quả của quá trình này. Việc mô phỏng sẽ được thực hiện trên hệ thống là một ngã tư có bùng binh như trong hình 3-22. Hình 3-22: Thử nghiệm mô phỏng tại môt ngã tư có bùng binh Kích thước của vùng giữa ngã tư là 24m x 24m và của 8 đoạn đường thẳng xung quanh là 8m x 16m, tức là chiều rộng là 8m và chiều dài là 16m. Các thử nghiệm mô phỏng sẽ được thực hiện với sự thay đổi về số người tham gia thông, trong đó có sự thay đổi về số thanh niên, số người già và số người trung tuổi. Để thực hiện các thử nghiệm này chúng tôi đã cài đặt sẵn một số thuộc tính đặc trưng của người lái phụ thuộc vào lứa tuổi và giới tính. Bảng 3-1 mô tả các thuộc tính của những người có tuổi tác và giới tính giới tính khác nhau. Tất nhiên, người sử dụng hoàn toàn có thể thay đổi các giá trị này như đã giới thiệu ở phần 3.5.1. Thanh niên Người trung tuổi Người già Nam Tốc độ tối đa: 50 km/h Tốc độ an toàn: 35 km/h Tăng tốc: 18 km/h/s Thời gian dự tính: 650 ms Tốc độ tối đa: 45 km/h Tốc độ an toàn: 31 km/h Tăng tốc: 16 km/h/s Thời gian dự tính: 800 ms Tốc độ tối đa: 40 km/h Tốc độ an toàn: 25 km/h Tăng tốc: 13 km/h/s Thời gian dự tính: 800 ms Nữ Tốc độ tối đa: 45 km/h Tốc độ an toàn: 32 km/h Tăng tốc: 15 km/h/s Thời gian dự tính: 650 ms Tốc độ tối đa: 43 km/h Tốc độ an toàn: 28 km/h Tăng tốc: 13 km/h/s Thời gian dự tính: 800 ms Tốc độ tối đa: 37 km/h Tốc độ an toàn: 22 km/h Tăng tốc: 10 km/h/s Thời gian dự tính: 800 ms Bảng 3-1: Thuộc tính của các người lái 3.6.1. Một số thử nghiệm Chúng tôi sẽ lần lượt trình bầy 4 thử nghiệm với các thay đổi về số người tham gia giao thông: Thử nghiệm với 80 người Thử nghiệm với 120 người Thử nghiệm với 160 người Mỗi thử nghiệm mô phỏng sẽ được thực hiện trong khoảng thời gian là 120 giây. 3.6.1.1. Thử nghiệm mô phỏng với 80 người Số thanh niên Số người trung tuổi Số người già Thời gian kiểm tra Số người về đích Thời gian di chuyển trung bình 80 0 0 120s 1104 8.3s 0 80 0 120s 982 9.5s 0 0 80 120s 844 10.5s 35 25 20 120s 987 9.3s Bảng 3-2: Thử nghiệm mô phỏng với 80 người Hình 3-23: Thử nghiệm mô phỏng với 80 người 3.6.1.2. Thử nghiệm mô phỏng với 120 người Số thanh niên Số người trung tuổi Số người già Thời gian kiểm tra Số người về đích Thời gian di chuyển trung bình 120 0 0 120s 985 13.5s 0 120 0 120s 862 14.6s 0 0 120 120s 826 15.7s 55 40 25 120s 916 14.5s Bảng 3-3: Thử nghiệm mô phỏng với 120 người Hình 3-24: Thử nghiệm mô phỏng với 120 người 3.6.1.3. Thử nghiệm mô phỏng với 160 người Số thanh niên Số người trung tuổi Số người già Thời gian kiểm tra Số người về đích Thời gian di chuyển trung bình 160 0 0 120s 800 20.2s 0 160 0 120s 670 24.0s 0 0 160 120s 675 24.2s 80 50 30 120s 742 22.3s Bảng 3-4: Thử nghiệm mô phỏng với 160 người Hình 3-25: Thử nghiệm mô phỏng với 160 người 3.6.2. Nhận xét các thử nghiệm Qua các thử nghiệm mô phỏng ta thấy, số lượng người tham gia giao thông khác nhau sẽ dẫn đến các kết quả khác nhau. Số lượng người di chuyển càng đông, việc di chuyển càng khó khăn và dẫn đến làm tăng thời gian di chuyển của các xe. Điều này thể hiện ở thông số thời gian di chuyển trung bình của các xe đã về đích. Với cùng một lượng người tham gia giao thông, nhưng tỉ lệ khác nhau về lứa tuổi của những người di chuyển khác nhau cũng dẫn đến những kết khác nhau. Do khả năng tăng tốc nhanh, những người thanh niên thường nhanh chóng tạo ra khoảng trống ở phía sau khi ra khỏi vùng đông người, nên làm sự lưu thông có phần nào tốt hơn. CHƯƠNG 4. TỔNG KẾT 4.1. Kết luận Từ sự tìm hiểu về các hệ thống mô phỏng giao thông đã được phát triển trước đây và phương pháp mô phỏng dựa trên agent, cũng như sự tìm hiểu về giao thông Việt Nam, chúng tôi đã nghiên cứu và xây dựng một hệ thống mô phỏng phù hợp với tình hình giao thông của nước ta. Đây là hệ thống mô phỏng mang tính vi mô, giúp mô phỏng một cách chi tiết sự di chuyển sự di chuyển của các phương tiện tham gia giao thông. Chúng tôi đã thiết kế những thành phần cơ bản của hệ thống đường xá, giúp tạo ra nhiều hệ thống đa dạng, phong phú, phức tạp giống với thực tế. Hơn nữa, các agent đóng vai trò người tham giao thông đã được xây dựng chi tiết với các thuộc tính đặc trưng phụ thuộc vào từng lứa tuổi, giới tính. Các thuộc tính này sẽ ảnh hưởng tới cách di chuyển của các phương tiện qua đó sẽ làm cho việc mô phỏng được chận thực. Người sử dụng hoàn toàn có thể tùy biến các thuộc tính sao cho sự di chuyển của các xe phù hợp với thực tế. Việc sử dụng thư viện đồ họa OpenGL cho phần hiển thị và cài đặt các giải thuật tính toán tỉ mỉ sự di chuyển các phương tiện đã giúp cho việc di chuyển của các phương tiện rất mượt mà, đồng thời cung cấp một số thông tin thống kê trong quá trình mô phỏng qua đó cung cấp một cái nhìn trực quan về các giải pháp phát triển giao thông. Chúng tôi đã cố gắng mô tả hệ thống một cách rõ ràng từ thiết kế các thành phần, mối liên hệ giữa các thành phần đến các giải thuật được sử dụng, hơn nữa các module cài đặt được phân chia vào các gói một cách có hệ thống nên hệ thống mô phỏng giao thông này có thể dễ dàng được nâng cấp và phát triển. 4.2. Hướng phát triển và mở rộng Hệ thống đã được nghiên cứu và xây dựng ở mức độ vi mô nhằm mô phỏng một cách chi tiết giao thông của Việt Nam. Tuy nhiên rất khó có thể áp dụng ngay vào thực tế do hệ thống còn thiếu một số chức năng quan trọng: Thứ nhất, đó là hệ thống mới chỉ mô phỏng sự di chuyển của phương tiện là xe máy. Hiện nay ở nước ta, có nhiều loại phương tiện giao thông khác nhau như xe đạp, xe máy, ô tô, xe buýt, … nên việc mô phỏng sự di chuyển của nhiều loại phương tiện khác nhau là rất cần thiết. Do đó, một trong những hướng phát triển là hệ thống cần bổ sung các loại agent đóng vai trò nhiều loại phương tiện khác nhau. Thứ hai, một trong những thành phần quan trọng của hệ thống giao thông chính là đèn giao thông và các tín hiệu giao thông. Chính vì vậy, việc bổ sung các thành phần đèn giao thông, các tín hiệu giao thông cũng như việc mô phỏng sự chấp hành các tín hiệu này của các agent tham gia giao thông cũng là hướng phát triển của hệ thống. Trong tương lai, chúng tôi sẽ cố gắng cải thiện các hạn chế, mở rộng các chức năng để có thể áp dụng hệ thống mô phỏng vào thực tế, nhằm phục vụ cho sự phát triển của hệ thống giao thông nước ta. Tài liệu tham khảo [1] Adina Magda Florea. Introduction to Multi-Agent Systems, In Proc. of Continuous Education Program on Intelligent Agents Technology and Knowledge Processing, Bucharest, 2001, tr. 49-60. [2] Agent Based Modeling FAQ [3] Charles M. Macal & Michael J. North. Introduction to Agent-based Modeling and Simulation. [4] Charles M. Macal & Michael J. North. Tutorial on Agent-Based Modeling and Simulation Part 2: How to model with Agents. Proceedings of the 38th conference on Winter simulation, 2006, tr. 73-83. [5] Differences between objects and agents [6] FERBER, J., 1999. Multi-agent Systems: Introduction to Distributed Artificial Intelligence. England: Addison Wesley. [7] Green Light District [8] James J. Odell. Objects and Agents Compared. Journal of Object Technology, vol.1, no.1, 2002, tr. 41-53. [9] Katia P. Sycara. Multiagent Systems. AI Magazine, 1998. [10] Matti Pursula, Simulation of Traffic System – An Overview. Journal of Geographic Information and Decision Analysis, vol.3, no.1, 1999, tr. 1-8. [11] Michael Wooldridge, An Introduction to Multiagent System (second edition). John Wiley & Sons, 2009, tr. 15-45. [12] Peter Stone and Manuela Velos. Multiagent Systems. A Survey from a Machine Learning Perspective, 1997. [13] Rahul Sukthankar, Dean Pomerleau & Charles Thorpe, SHIVA: Simulated Highways for Intelligent Vehicle Algorithms. Proceedings of Intelligent Vehicles '95, September, 1995, tr. 332-337. [14] Thomas Fotherby. Visual Traffic Simulation, 2002 [15] Todd Sundsted. An introduction to agents