CHƯƠNG 1: GIỚI THIỆU 1.1 Đặt vẫn đề Hoạch định đường di là bài toán nhận dạng đường di sao cho robot đi đến được đích với bản đồ và đích đến biết trước. Một số phương pháp kinh điển như: phương pháp trường thé năng, phương pháp phân giải 6, phương pháp bản dé đường. Mỗi phương pháp đều có ưu và nhược điểm. Phương pháp trường thế năng có nhược điểm khiến robot rơi vào điểm tối thiểu cục bộ.
Phương pháp phân giải ô trở nên phức tạp khi môi trường có nhiều vật cản, tuy nhiên áp dụng tốt các giải thuật tìm kiếm đường đi. Phương pháp bản đồ đường đơn giản nhưng không cho kết quả tối ưu, hoặc nếu tối ưu thì không an toàn do robot di chuyển gan vật cản. Một phương pháp tìm đường rất phổ biến là A* đã chứng minh rất thành công khi áp dụng vào xe tự hành của Stanford trong giải đấu DARPA Urban Challenge. A* là giải thuật sử sung nhiều trong lĩnh vực trí tuệ nhân tạo trong việc tự động lên kế hoạch dé đạt được mục đích đề ra.
Đặc điểm của A* là xây dựng các hàm chi phí thực kết hợp với chi phí tính toán dựa trên kinh nghiệm, nên đã cho kết quả tối ưu cho các bài toán bao gém bài toán hoạch định đường đi với chi phí khoảng cách nhỏ nhất. Để hoạch định được đường di, robot cần biết trước bản đồ đang hoạt động. Có hai loại bản đồ sử dụng trong lĩnh vực robot di động: bản đồ lưới và dạng đồ thị. Mỗi ban đồ đều có ưu, nhược điểm riêng.
Bản đồ dạng đô thị với ưu điểm là mô ta môi trường tong quát, chia môi trường thành những vùng nhỏ liên kết với nhau. Dé robot hoạt động được trong ban đồ này cần bố sung thêm các thông tin về môi trường (Feature base) như: vị trí tường, các góc của phòng, cửa đi,. Ban đồ dạng lưới mô tả môi trường là tập hợp các ô mắt lưới, mỗi ô mang một giá trị xác suất đánh giá mức độ trống của 6. Bản đồ lưới như là ảnh xám mô tả thông tin môi trường, nên có thể áp dụng các giải thuật xử lý ảnh hỗ trợ cho bài toán tìm đường đi.
Xét về mặt tìm kiếm đường đi, bản đồ dạng đồ thị áp dụng tốt các giải thuật tìm kiếm, bản đồ lưới phức tạp hơn vì số lượng các ô mắt lưới rất lớn nên ảnh hưởng đến tốc độ tìm kiếm và tài nguyên máy tính. Nếu kết hợp được hai ban đỗ này vào hoạch định đường di sẽ làm giảm thời gian tìm kiếm rất nhiều. Mục tiêu của dé tài là kết hợp hai loại bản đồ trên dé hoạch định đường đi cho robot, trong đó áp dụng giải thuật A* vào tìm kiếm đường đi cho cả hai ban đồ. Xây dựng bản đồ can khối lượng lớn công việc và giải thuật, nên trong giới hạn dé tài, tác giả mô phỏng ban dé lưới nhờ đọc camera gan trên bản đồ.
Dựa trên bản đồ lưới, sử dụng các công cụ xử lý ảnh để xây dựng bản đồ dạng đồ thị. Giải thuật xây dựng bản đồ dạng đồ thị xây dựng hoàn toàn tự động với bat cứ thay đổi nào từ bản đỗ lưới. Xây dựng mô hình tác nhân có thé học, xây dựng lại ban đồ dạng đồ thị, có thé tự hoạch định đường đi tối ưu cho robot khi bản đồ thay đổi. Việc xây dựng bản dé dạng đồ thi rất quan trong vì giúp chia nhỏ bản đồ lưới, giúp giảm khối lượng tìm kiếm.
Thay vì tìm kiếm trên toàn bản đồ lưới từ điểm xuất phát đến điểm đích, sau khi được phân vùng, bài toán trở thành tìm kiếm trên từng vùng nhất định theo kết quả tìm kiếm vùng trên đồ thi. Như vậy, bài toán cho lời giải tối ưu cục bộ vì chỉ cho kết quả tối ưu theo từng vùng. Từ kết quả hoạch định đường đi phải xây dựng được quỹ đạo để robot bám theo. Có rất nhiều phương pháp xây dựng quỹ đạo, trong đó sử dụng các hàm nội suy bậc cao để lập quỹ đạo.
Các hàm nội suy thường sử dụng là Spline bậc ba, các hàm bậc năm, bậc bảy, các hàm nội suy bậc cao có ưu điểm là đạo hàm bậc một trơn, bậc hai liên tục. Trong giới hạn đề tài, tác giả sử dụng phương pháp nội suy Spline bậc ba, với ưu điểm là dễ dàng lập quỹ đạo do sử dụng các công cụ giải toán ma trận, với đạo hàm bậc một trơn (vận tốc) và đạo hàm bậc hai liên tục (gia tốc).2 Tong quan Hoach dinh duong di cho robot la dé tai đã được nghiên cứu từ lâu, với rất nhiều phương pháp đã được xây dựng [16]. Phương pháp hoạch định trong bản đồ đường (Road map). Bản đồ đường là tập hợp mạng các đường thắng và đường cong trong môi trường làm việc của robot.
Có thé chỉ ra hai bản đỗ đường thường dùng là: đô thị trực quan (Visibility graph) và biêu đô Voronoi (Voronoi diagram).1: Hoach dinh theo ban dé duong: a) Đồ thị trực quan, b) Biểu đồ Voronoi Phương pháp đồ thị trực quan xây dựng không gian vật cản, giả sử vật cản là đa giác. Bao gồm các cạnh nối các cặp đỉnh của đa giác (bao gồm cả vị trí đầu và đích). Những đường thang này là đường ngăn nhất nối giữa các đỉnh. Nhiệm vụ của m6 hình hoạch định là tìm ra tập hợp các cạnh để đi từ điểm xuất phát đến đích sao cho quãng đường là ngắn nhất.
Ưu điểm của bản đỗ trực quan là dé dàng áp dụng cho robot. Nhược điểm là khi vật cản tăng lên, các đỉnh đa giác tăng theo, do đó tập hợp các cạnh rất lớn, nên việc tìm kiếm đường đi sẽ phức tạp. Các kết quả đường đi thường có xu hướng làm cho robot gan vật cản, dẫn đến không an toàn. Kết quả hoạch định trong đồ thị trực quan là tối ưu.
Phương pháp biéu đồ Voronoi xây dựng đường Voronoi như sau: với mỗi điểm trong môi trường, tìm khoảng cách đến vật cản gần nhất. Voronoi là tập hợp các điểm trên, có khoảng cách đến hai (hoặc lớn hơn) vật cản gan nhat bang nhau. Nhu vậy, đường Voronoi có xu hướng tránh xa vật cản. Với tinh chất này kết qua hoạch định không phải là tối ưu.
Phương pháp hoạch định sử dụng phép phân giải ô (Cell decomposition). Phân chia môi trường thành các 6 trống va ô có vật cản. Xác định xem các 6 trong có thé liên kết được với nhau, xây dựng nên bản đồ kết nối (bản đồ dạng đồ thị). Sau đó xác định điểm đích và xuất phát thuộc các ô nào trong bản đồ.
Xây dựng giải thuật tìm kiếm tìm đường đi giữa các vùng, có thể tìm đến trung điểm của đường biên mỗi vùng hoặc dùng giải thuật đi theo tường (wall — following). Có hai phương pháp xây dựng là: Phép phân giải ô chính xác (Exact cell decomposition) và phép phân giải xấp xi (Approximate cell decomposition).2: Hoạch định theo phép phân giải tương đối Trong phép phân giải ô chính xác, các ô phân chia chính xác thành ô trống và ô có vật cản. Nhược điểm của phương pháp này là khi vật cản nhiều số ô phân chia sẽ nhiều, khi đó giải thuật tìm kiếm sẽ phức tạp, mất nhiều thời gian. Ngược lại, nếu môi trường thưa sẽ là lợi thế cho giải thuật.
Trong phép phân giải xấp xỉ. Nếu kích thước các ô là có định, phép phân giải này tạo nên bản đồ mất lưới (hình 1.6), là bản đồ rất phô biến trong robot di động. Môi trường được chia thành các ô có kích thước băng nhau, mỗi ô chứa giá tri xác suât đánh giá mức trông của 6. Hoạch định trong trường thế năng (Potential field).
Phương pháp này xem robot như là một chất điểm chịu ảnh hưởng của trường thế năng nhân tạo. Trong trường này, vật cản tạo ra trường day (Repulsive potential), điểm đích tao ra trường hấp dẫn (Attractive potential). Tổng hợp các lực tác động lên robot sẽ đây robot di chuyển. Phương pháp này không chỉ là hoạch định mà còn vạch ra luật điều khiến vì lực tác động vào robot có hướng và có giá trị nên sẽ đây robot đi theo hướng của lực với gia tốc phụ thuộc vào độ lớn của lực.
Nhược điểm của phương pháp này là rất dé rơi vào trạng thái tối cực tiểu cục bộ. Rất nhiều phương pháp mở rộng trường thế năng được đưa ra, mục đích là giải quyết nhược điểm của trường thế năng. Trong đó có phương pháp trường thé năng mở rộng. BO sung thêm hai trường: trường thé năng xoáy (rotation potential field) và trường thé năng nhiệm vu (task potential field).
Trường thé năng xoáy tạo ra bởi lực day của trường đây và khoảng cách tới vật cản. trong đó giải thuật A* đã được áp dụng vào hoạch định đường đi cho xe tự hành của đại học Stanford tham dự DARPA Urban Challenge và cho kết quả tốt. Việc áp dung tác nhân thông minh của lĩnh vực trí tuệ nhân tạo vào robot còn rất mới. Trong đó, các nghiên cứu chủ yếu xây dựng cho xe lăn thông minh, một dạng robot di động, nhưng đòi hỏi nhiều tác vụ phức tạp hơn.
Có nhiều hướng nghiên cứu về các tác vụ cơ bản cho xe lăn thông minh, bao gồm: dẫn đường, học bản đồ, hoạch định đường di,. Trong những năm gan đây, các dé tài tập trung vào xây dựng xe lăn dạng mô đun tích hợp [1] dựa trên co sở các tác nhân thông minh. 10 Nhóm tác giả Rodrigo Antonio Marques Braga xây dựng mô hình phan cứng cho xe lăn dạng mô dun [1] (Hình 1. M6 đun hoạch định thông minh sử dụng giải thuật A* để tìm kiếm đường đi ngắn nhất.
Sử dụng ngôn ngữ định nghĩa miền hoạch định (Planning domain definition language (PDDL)) để hoạch định các tác vu cho xe lăn. Mô đun dẫn đường sử dụng các cảm biến khoảng cách để định vị và biểu diễn ban đồ. Tác nhân thông minh đảm nhận các nhiệm vụ: hoạch định tác vụ, theo dõi thời gian thực, hoạch định đường di, nó tương tác với các tác nhân khác như: tác nhân điều khiến, tác nhân cảm biến. Tác nhân điều khiến thực hiện chức năng điều khiến cơ bản: đi theo hành lang, đi theo đường thăng, xoay, di chuyển điểm — điểm.
Tác nhân nhận thức đảm nhận nhiệm vụ: biểu biễn bản đồ, định vị đồng thời quản lý các cảm biến. Các tác nhân tương tác qua lại bằng ngôn ngữ giao tiếp tác nhân (Agent communication language (ACL)). Tuy nhiên, tác giả chưa đề cập đến van dé xây dựng mô dun học ban đồ, giúp cho việc hoạch định đường đi. II Interface Agent Intelligence Agent Multimodal E Planning Basic : Cooperation Configuration § Collaboration Sensor Tactic Control Mapping : Basic Control Hình 1.