Ý nghĩa khoa học
Hoạch định quỹ đạo là bài toán lớn và được ứng dụng rất rộng rãi trong nhiều lĩnh vực khác nhau của cuộc sống
Tuy nhiên, việc giải bài toán này luôn có những khó khăn nhất định:
Việc lập kế hoạch đường đi trong môi trường động như thế giới thực gặp nhiều thách thức, do các đối tượng có khả năng gây va chạm không cố định và luôn di chuyển.
Việc xác định quỹ đạo di chuyển cần phải phù hợp với loại phương tiện điều khiển Chẳng hạn, quỹ đạo từ A đến B cho ô tô 4 bánh khác với quỹ đạo cho xe Segway RMP; ô tô không thể thực hiện những khúc cua gấp 90 độ, trong khi xe Segway lại có khả năng này.
Hoạch định một chuyển động được coi là hoàn thành khi trong một khoảng thời gian nhất định, nó cung cấp giải pháp xử lý và báo cáo chính xác về chuyển động, điều này rất phức tạp Hầu hết các thuật toán sử dụng đều dựa trên các thuật toán hình học, dẫn đến việc xác định quỹ đạo cuối cùng thông qua những phép tính phức tạp.
Việc xây dựng và giải quyết bài toán hoạch định đường đi cho robot di động không chỉ giúp cải thiện thuật toán điều khiển xe lăn mà còn mở ra những góc nhìn và cách tiếp cận mới trong nghiên cứu và phát triển Điều này có thể dẫn đến những hướng nghiên cứu tối ưu hơn cho việc điều khiển xe lăn thông minh cũng như robot tự hành tại Việt Nam.
Nghiên cứu tổng quan
Tổng quan bài toán hoạch định quỹ đạo
Quy hoạch quỹ đạo là quá trình di chuyển từ điểm A đến điểm B, đồng thời tránh các vật cản trong khoảng thời gian nhất định Phương pháp tính toán có thể là rời rạc hoặc liên tục Đây là một lĩnh vực quan trọng trong ngành robot, đóng vai trò then chốt trong việc tự động hóa các phương tiện.
Có 2 thuật ngữ cơ bản:
Quy hoạch đường đi là quá trình xác định quỹ đạo hoặc lộ trình cho robot, nhằm tránh các vật cản mà không cần phụ thuộc vào thời gian Điều này có nghĩa là không cần xác định thời gian di chuyển từ điểm A đến điểm B.
Quy hoạch quỹ đạo: đưa ra quỹ đạo hay đường đi, tránh vật cản, từ A đến B và trong thời gian nhất định
Quy hoạch quỹ đạo là quá trình thiết lập đường dẫn cho robot, dựa trên các yếu tố như vận tốc, chuyển động và đặc tính động học, nhằm tối ưu hóa việc di chuyển.
1.2.1.1/ Khái niệm : trong đó, SO(2) là nhóm trực giao của phép quay 2 chiều [23] Mỗi một cấu hình sẽ được biểu diễn bởi 3 thông số (x,y,)
Robot được coi là hình khối 3 chiều với khả năng di chuyển và xoay trong không gian làm việc 3 chiều Nhóm Euclidean cho robot được biểu diễn là SE(3) = R³ * SO(3) Để xác định một cấu hình của robot, cần 6 thông số, bao gồm 3 thông số (x, y, z) cho vị trí và 3 góc Euler (α, β, γ) cho sự xoay.
Hình 1.1 Minh họa cho không gian làm việc
Cfree là không gian trống, nơi không có vật cản, nhưng việc xác định hình dạng chính xác của Cfree thường gặp khó khăn Tuy nhiên, có thể dễ dàng kiểm tra một cấu hình trong Cfree bằng cách sử dụng động học thuận để xác định vị trí hình học của robot Việc phát hiện va chạm được thực hiện khi hình dạng của robot va chạm với hình dạng của môi trường, cho phép xác định xem một cấu hình có vật cản hay không dựa vào chuyển động và cảm biến phát hiện vật cản của robot.
Hình 1.2 Minh họa cho C free và Cobs
Các phương pháp hoạch định quỹ đạo
Có nhiều thuật toán khác nhau, nhưng chúng có thể được phân loại thành các phương pháp cơ bản Để giải quyết vấn đề trong không gian ít chiều, có thể áp dụng phương pháp hoạch định dựa vào lưới bằng cách phủ một mạng lưới lên bề mặt không gian cấu hình, hoặc sử dụng các thuật toán hình học để tính toán hình khối và các kết nối trong không gian.
Hoạch định chuyển động trong hệ thống nhiều chiều với điều kiện ràng buộc phức tạp là một thách thức lớn trong tính toán Phương pháp trường thế năng rất hiệu quả nhưng dễ dẫn đến các cực trị cục bộ Ngược lại, phương pháp hoạch định dựa trên lấy mẫu có khả năng tránh các cực trị này và giải quyết nhiều vấn đề nhanh chóng Tuy nhiên, phương pháp này không thể xác định việc không tồn tại đường dẫn từ điểm đầu đến điểm đích, mặc dù nó cung cấp một chỉ số xác suất báo hiệu sự thất bại, chỉ số này giảm dần về 0 khi thời gian sử dụng tăng lên.
Phương pháp này có thể được sử dụng khi hoạch định chuyển động trong các bài toán phức tạp
1.4/ Tính cấp thiết của đề tài:
Việc xây dựng quỹ đạo và đường đi không chỉ quan trọng trong việc điều khiển robot mà còn được áp dụng rộng rãi trong các phương tiện giao thông như ô tô và xe lửa, cũng như trong lĩnh vực quân sự và hàng không vũ trụ Đặc biệt, việc hoạch định chính xác quỹ đạo là yếu tố quyết định đến sự thành công của các nhiệm vụ phóng tên lửa và tàu con thoi, cũng như trong việc điều khiển máy bay không người lái Vì vậy, bài toán hoạch định quỹ đạo đang thu hút sự quan tâm lớn từ các nhà khoa học trên toàn thế giới, mặc dù vẫn còn khá mới mẻ tại Việt Nam.
Kết quả của đề tài sẽ hỗ trợ việc phát triển và chế tạo xe lăn thông minh tại Việt Nam, phục vụ hiệu quả cho các bệnh viện, người khuyết tật và người cao tuổi.
Ứng dụng công nghệ vào việc hỗ trợ và điều khiển các phương tiện giao thông cá nhân như xe tải và ô tô có thể góp phần đáng kể vào việc giảm tỷ lệ tai nạn giao thông, hiện đang ở mức cao tại Việt Nam.
Việc phát triển phương pháp hoạch định đường đi cho robot di động là rất cần thiết và mang tính đột phá trong lĩnh vực robot tự hành tại Việt Nam.
Như đã giới thiệu ở trên, có ba phương pháp chính thường được áp dụng cho các bài toán hoạch định quỹ đạo
1.5/ Các phương pháp hoạch định quỹ đạo:
1.5.1/ Hoạch định trường thế năng (Potential Field Planning):
Vùng thế năng trên bản đồ được xác định bởi các điểm có giá trị, với mục tiêu là những vị trí có giá trị thấp nhất, và giá trị sẽ tăng dần theo khoảng cách từ điểm đó đến mục tiêu Các vật cản được gán giá trị cao, do đó, nhiệm vụ của robot là di chuyển đến các vị trí tiềm năng liền kề có giá trị thấp, nhằm hướng tới mục tiêu.
Hình 1.3 Minh họa cho trường thế năng
Một phương pháp hiệu quả để xử lý cấu hình của robot trong trường thế năng là kết hợp giữa việc hướng tới mục tiêu và tránh vật cản Kết quả của phương pháp này là tạo ra một quỹ đạo di chuyển, với ưu điểm là giảm thiểu lượng tính toán cần thiết Tuy nhiên, kỹ thuật này có nhược điểm là dễ rơi vào bẫy của các cực trị cục bộ, dẫn đến khả năng không tìm ra được đường đi tối ưu.
Một trong những kỹ thuật hiệu quả để tránh mắc kẹt trong các cực trị cục bộ là kết hợp hoạch định phân tách Voronoi với hoạch định theo trường thế năng Việc xây dựng biểu đồ Voronoi không chỉ giúp tối ưu hóa quá trình hoạch định mà còn mang lại lợi thế vượt trội trong việc quản lý quần thể.
Hình 1.4 Quỹ đạo khi kết hợp hoạch định Voronoi và trường thế năng
1.5.2/ Hoạch định dựa trên việc lấy mẫu (Sampling Based Planning):
Phương pháp đường bản đồ (roadmap) là một kỹ thuật hoạch định đường đi dựa trên việc lấy mẫu, trong đó các thuật toán sẽ tái hiện không gian cấu hình qua một lộ trình từ các điểm mẫu Đầu tiên, N điểm cấu hình được lấy mẫu trong không gian C, và chỉ giữ lại những điểm nằm trong Cfree, được coi là điểm nút Một đường tuyến tính PQ được hình thành bằng cách nối các điểm nút này lại, đảm bảo PQ nằm trong Cfree Sau đó, đường này được kiểm tra để phát hiện va chạm trong Cfree Để tìm đường nối từ điểm đầu S đến điểm cuối G, các điểm này sẽ được thêm vào lộ trình Nếu đường đi trong lộ trình kết nối thành công từ S đến G, việc hoạch định được coi là thành công và đường đi sẽ được trả về Nếu không, có thể không tồn tại đường đi trong Cfree hoặc việc lấy mẫu từ các điểm nút chưa đủ.
Hình 1.5 Minh họa quỹ đạo a) Quỹ đạo đúng b) Quỹ đạo sai
Hình 1.6 Minh họa cho phương pháp đường bản đồ
Phương pháp này hiệu quả trong không gian nhiều chiều và có thời gian chạy không theo cấp số nhân như các thuật toán tổ hợp, giúp dễ dàng thực hiện Nó cung cấp một chỉ số xác suất cho khả năng tìm ra giải pháp, với xác suất tiệm cận 1 khi thời gian sử dụng tăng lên Tuy nhiên, phương pháp này không thể xác định được trường hợp không tồn tại giải pháp.
1.5.3/ Hoạch định dựa vào lưới tọa độ (Grid Based Planning):
Việc lập kế hoạch di chuyển cho robot dựa trên việc tạo ra một mạng lưới trên bản đồ, trong đó mỗi cấu hình tương ứng với một điểm lưới Robot sẽ di chuyển từ điểm lưới này đến điểm lưới khác trong vùng C free để kiểm tra và phát hiện vật cản Các hành động di chuyển này được rời rạc hóa, và sau đó, một thuật toán tìm kiếm sẽ được áp dụng để xác định lộ trình từ điểm khởi đầu đến mục tiêu.
Hình 1.7 Minh họa cho phương pháp hoạch định theo lưới
Các phương pháp tiếp cận này yêu cầu thiết lập độ phân giải cho lưới Lưới thô với độ phân giải thấp giúp tìm đường nhanh hơn, nhưng có thể bỏ qua những lối đi trong các vùng hẹp của Cfree Ngược lại, lưới có độ phân giải cao cần nhiều bộ nhớ cho tính toán, và số lượng điểm lưới tăng theo cấp số nhân theo không gian cấu hình, khiến phương pháp này không phù hợp cho các vấn đề không gian cấu hình lớn và nhiều chiều.
Các phương pháp truyền thống trong hoạch định dựa vào lưới thường xác định đường đi với sự thay đổi hướng bị giới hạn bởi các bội số của góc cơ sở, dẫn đến kết quả không tối ưu Để tìm ra những lộ trình ngắn hơn, cần phải lan truyền thông tin dọc theo biên của lưới mà không bị giới hạn, từ đó giúp tìm kiếm nhanh chóng và hiệu quả hơn.
Cách tiếp cận dựa vào lưới tọa độ giúp tìm kiếm thông tin về không gian cấu hình khi có sự thay đổi, cho phép robot điều chỉnh đường dẫn tiếp theo Bằng cách nâng cao phương thức phỏng đoán, các thuật toán lập kế hoạch có thể thực hiện nhanh chóng dựa trên kinh nghiệm từ những lần lập kế hoạch trước, đồng thời tăng tốc độ đưa ra đường dẫn hiện tại.
1.6/ Các công cụ giải bài toán hoạch định và những công trình liên quan :
