Luận văn Xây dựng và đánh giá một hệ thống mô phỏng giao thông Việt Nam

1 ĐẠ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 2 ĐẠ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 i 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. ii 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 iii MỤC LỤC MỞ ĐẦU ..............................................................................................................................1  CHƯƠNG 1: MÔ PHỎNG GIAO THÔNG ........................................................................3  1.1. Giới thiệu .................................................................................................................3  1.2. Hệ thống mô phỏng giao thông trực quan ...............................................................4  1.2.1. Mô hình hệ thống giao thông .........................................................................5  1.2.2. Mô hình điều khiển sự di chuyển các xe trên đường .....................................5  1.2.3. Mô hình thống kê ...........................................................................................6  1.3. Mô phỏng xe thông minh trên đường cao tốc..........................................................6  1.3.1. Mô hình mạng lưới đường cao tốc.................................................................7  1.3.2. Mô hình xe cộ ................................................................................................8  1.4. Hệ thống mô phỏng đèn giao thông.........................................................................9  1.5. Kết luận ..................................................................................................................10  CHƯƠNG 2: MÔ HÌNH DỰA TRÊN AGENT ................................................................11  2.1. Agent và hệ thống đa agent....................................................................................11  2.1.1. Agent ............................................................................................................11  2.1.2. Hệ thống đa agent – MAS............................................................................12  2.2. Mô hình dựa trên agent ..........................................................................................13  2.2.1. Khái niệm về mô hình dựa trên agent – ABM.............................................13  2.2.2. Sự khác nhau giữa agent và đối tượng.........................................................14  2.2.3. Một số ứng dụng của ABM..........................................................................14  2.2.4. Cách xây dựng một ABM ............................................................................15  2.3. Kết luận ..................................................................................................................15  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 ..............................................................................................16  3.1. Một số đặc điểm của giao thông Việt Nam ...........................................................16  3.2. Các ý tưởng xây dựng hệ thống .............................................................................16  3.2.1. Xây dựng hệ thống đường xá.......................................................................17  3.2.2. Xây dựng agent đóng vai trò người tham gia giao thông ............................20  3.3. Mô tả hệ thống .......................................................................................................24  iv 3.3.1. Các thành phần chính của hệ thống .............................................................24  3.3.2. Các thuật toán được sử dụng........................................................................28  3.4. Cài đặt hệ thống mô phỏng ....................................................................................34  3.5. Giới thiệu chương trình mô phỏng.........................................................................36  3.5.1. Chế độ thiết kế .............................................................................................36  3.5.2. Chế độ mô phỏng .........................................................................................40  3.6. Một số thử nghiệm và nhận xét..............................................................................41  3.6.1. Một số thử nghiệm .......................................................................................42  3.6.2. Nhận xét các thử nghiệm .............................................................................46  CHƯƠNG 4. TỔNG KẾT..................................................................................................47  4.1. Kết luận ..................................................................................................................47  4.2. Hướng phát triển và mở rộng.................................................................................47  Tài liệu tham khảo ..............................................................................................................49  v 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 vi 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ỳ ...............31  Hình 3-12: Agent cảm nhận được va chạm với agent khác ...............................................32  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 ......33  Hình 3-15: Agent kiểm tra lựa chọn đánh lái để tránh va chạm ........................................34  Hình 3-16: Giao diện chương trình ở chế độ thiết kế.........................................................37  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 ý...........38  Hình 3-18: Hộp thoại chọn các thành phần đường dựng sẵn .............................................38  vii Hình 3-19: Hộp thoại tùy chọn số người tham gia giao thông...........................................39  Hình 3-20: Hộp thoại tùy chọn các thuộc tính của người lái .............................................39  Hình 3-21: Giao diện chương trình ở chế độ mô phỏng ....................................................40  Hình 3-22: Thử nghiệm mô phỏng tại môt ngã tư có bùng binh........................................41  Hình 3-23: Thử nghiệm mô phỏng với 80 người ...............................................................43  Hình 3-24: Thử nghiệm mô phỏng với 120 người .............................................................44  Hình 3-25: Thử nghiệm mô phỏng với 160 người .............................................................45  Bảng 3-1: Thuộc tính của các người lái .............................................................................42  Bảng 3-2: Thử nghiệm mô phỏng với 80 người.................................................................43  Bảng 3-3: Thử nghiệm mô phỏng với 120 người...............................................................44  Bảng 3-4: Thử nghiệm mô phỏng với 160 người...............................................................45  1 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ô 2 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. 3 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 4 đẩ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 5 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