Xem mẫu
- Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 09-10/8/2018
DOI: 10.15625/vap.2018.00038
MỘT GIẢI PHÁP KỸ THUẬT THIẾT LẬP KẾ HOẠCH CHUYỂN ĐỘNG
CHO XE TỰ HÀNH
Quách Hải Thọ1, Huỳnh Công Pháp2, Phạm Anh Phương3
1
Tổ Cơ sở Ngành, Trường Đại học Nghệ thuật, Đại học Huế
2
Khoa Công nghệ Thông tin và Truyền thông, Đại học Đà Nẵng
3
Khoa Tin học, Trường Đại học Sư phạm, Đại học Đà Nẵng
haitho37@gmail.com,hcphap@gmail.com,paphuong@yahoo.com
TÓM TẮT: Bằng phương pháp tiếp cận dựa trên mẫu, để tạo ra quỹ đạo tối ưu từ tập các ứng viên quỹ đạo nhằm mục đích cải
thiện hiệu suất và tăng cường khả năng lập kế hoạch chuyển động dựa trên các thông tin nhận được từ hệ thống cơ sở hạ tầng giao
thông và các đối tượng khác trên đường thông qua hệ thống các thiết bị cảm biến. Trong bài báo này, để xử lý tính không chắc chắn
trong dữ liệu tri giác và cấu trúc hệ thống xe, chúng tôi đề xuất một giải pháp lập kế hoạch chuyển động cho xe tự hành sử dụng cấu
trúc cơ bản của bộ lọc phần tử với bốn bước cơ bản được thực hiện lặp lại cho đến khi tìm được quỹ đạo tối ưu, từ đó đánh giá giải
pháp và định hướng nghiên cứu ứng dụng về bài toán xe tự hành trong thực tế.
Từ khóa: Autonomous vehicle, particle filter, path planning, motion planning, intelligent transportation systems.
I. GIỚI THIỆU
Trong những năm gần đây, nhiều nghiên cứu về bài toán xe tự hành đã được thực hiện dựa trên các thành phần
cơ bản như: hệ thống định vị, tri giác môi trường, lập kế hoạch và điều khiển [1,11,20]. Trong các thành phần này, vấn
đề lập kế hoạch chuyển động là một chức năng quan trọng để xác định quá trình di chuyển của xe, nó cung cấp mục
tiêu sẽ đến của xe bằng cách sử dụng thông tin thu nhận được từ môi trường và hệ thống định vị. Do đó, các thành phần
trong bộ lập kế hoạch không chỉ xét đến những yếu tố của xe mà còn phải xét đến những thay đổi của môi trường qua
dữ liệu tri giác thu nhận được trong hệ thống nhằm đảm bảo độ tin cậy và an toàn khi tham gia giao thông.
Để tìm được giải pháp xác định đường đi tối ưu trong điều kiện môi trường phức tạp, đã có nhiều nghiên cứu
cho bài toán này như kỹ thuật trường thế, kỹ thuật tìm kiếm trên đồ thị hoặc kỹ thuật dựa trên mẫu [5]. Trong các kỹ
thuật này, kỹ thuật dựa trên mẫu được sử dụng rộng rãi cho các không gian đường có cấu trúc bằng cách giảm bớt một
số giải pháp tính huống nhằm đạt được hiệu suất thời gian thực khi xử lý; kỹ thuật dựa trên mẫu thực hiện việc tạo ra
và sắp xếp tập các ứng cử viên quỹ đạo nên có khả năng không làm ảnh hưởng đến không gian tìm kiếm ở các vùng
được quan tâm. Do đó, kỹ thuật dựa trên mẫu đã trở thành một giải pháp được sử dụng khá phổ biến khi xây dựng kế
hoạch chuyển động của xe tự hành so với các giải pháp kỹ thuật khác.
Tuy nhiên, một thách thức đối với các giải pháp lập kế hoạch chuyển động dựa trên mẫu là phải làm thế nào để
lấy mẫu các ứng viên trong không gian quỹ đạo một cách hiệu quả. Để giải quyết vấn đề này, các phương pháp tiếp cận
khác nhau dựa trên mẫu đã được nghiên cứu như lấy mẫu không gian đầu vào, lấy mẫu không gian trạng thái và lấy
mẫu mạng lưới trạng thái [14]; từ những nghiên cứu này, có thể thấy những ràng buộc non-holonomic của xe và điều
kiện biên của môi trường giao thông có thể được xem là có tác dụng hiệu quả trong việc lựa chọn các mẫu ứng viên
[5]. Vì tất cả các phương pháp dựa trên mẫu, về cơ bản chỉ đạt được cận dưới của quỹ đạo mục tiêu cuối cùng bằng các
kỹ thuật tối ưu, cho nên phương pháp này đòi hỏi phải có một lượng tài nguyên đủ lớn nhằm có được một số lượng lớn
các ứng viên để tìm được quỹ đạo tối ưu toàn cục.
Ngoài ra, hầu hết các kỹ thuật dựa trên mẫu trước đây đã thực hiện cách sử dụng cách tiếp cận tất định, là cách
tiếp cận có độ phức tạp tính toán ít để tìm ra quỹ đạo đáng tin cậy và được sử dụng để giải quyết bài toán tránh va
chạm trong các giải pháp lập kế hoạch chuyển động [14,16]. Nhưng cách tiếp cận tất định cần phải sử dụng các hệ
thống cảm biến có chất lượng cao với độ nhiễu ít, bởi vì chúng không có mô hình rõ ràng với những dữ liệu tri giác thu
được để ước lượng các va chạm được chính xác.
Để giải quyết có hiệu quả những khó khăn trên, cách tiếp cận xác suất trong giải pháp lập kế hoạch chuyển động
đã được nghiên cứu với những thuật toán khác nhau như tiếp cận Bayes [2], phương pháp Monte Calor [4] và quy trình
Markov [7], các thuật toán này có thể xử lý một mô hình hệ thống không đầy đủ và các phép đo cảm biến với dữ liệu
tri giác không chắc chắn. Tuy nhiên, các phương pháp tiếp cận xác suất này đã gặp vấn đề trở ngại do sự không thống
nhất giữa giải pháp quy hoạch chuyển động bằng kỹ thuật tối ưu tất định và tri thức môi trường xác suất. Chẳng hạn
như hệ thống cảm biến thu nhận dữ liệu tri giác quy định hàm mật độ xác suất của các chướng ngại vật di động (như
các loại xe), trong khi đó các thuật toán lập kế hoạch chuyển động dựa trên mẫu lại cần sự chuyển động các bất định từ
khu vực này sang khu vực khác.
Trong bài báo này, chúng tôi đề xuất một giải pháp lập kế hoạch chuyển động với mục tiêu đặt ra không chỉ
cải thiệu hiệu quả tính toán mà còn xử lý tính bất định trong dữ liệu tri giác của môi trường và hệ thống phương tiện
đề xuất.
- 282 MỘT GIẢI PHÁP KỸ THUẬT THIẾT LẬP KẾ HOẠCH CHUYỂN ĐỘNG CHO XE TỰ HÀNH
Phần tiếp theo của bài báo chúng tôi sẽ giới thiệu các nguyên tắc cơ bản để xây dựng kế hoạch chuyển động và
các thuật toán liên quan, từ đó chúng tôi đề xuất giải pháp lập kế hoạch chuyển động dựa trên cấu trúc của bộ lọc phần
tử. Tiếp theo là phần thực nghiệm và kết luận với một số đề xuất cho bài toán xe tự hành.
II. XÂY DỰNG GIẢI PHÁP LẬP KẾ HOẠCH CHUYỂN ĐỘNG CHO XE TỰ HÀNH
Trong bài toán lập kế hoạch chuyển động của xe tự hành, các yếu tố cần được tính toán và xem xét như hệ thống
cơ học vận hành của xe, những hạn chế về môi trường hoạt động như cấu trúc hệ thống đường giao thông, các chướng
ngại vật trên đường ... với mục tiêu của bài toán lập kế hoạch là tìm ra một quỹ đạo có tính an toàn và khả thi, thì bài
toán này cần xét đến các điều kiện biến thiên theo thời gian và quỹ đạo được tạo ra cuối cùng là một tập chứa các
thông tin của cấu trúc đường hình học (gồm có vị trí ( ), góc ban đầu và độ cong ) và thông tin biến động của
chuyển động (thời gian , vận tốc , gia tốc và độ lệch ).
Hình 1. Mô hình về lập kế hoạch chuyển động
Để tìm được quỹ đạo chuyển động (quỹ đạo tối ưu và an toàn) thì độ chính xác của hệ thống định vị và dữ liệu
tri giác môi trường là rất quan trọng. Nhưng do hạn chế về thiết bị cảm biến và vấn đề nhiễu của môi trường thu nhận;
do đó yếu tố không chắc chắn hay sai lệch định vị và dữ liệu tri giác môi trường cần phải được xét đến trong quá trình
xây dựng kế hoạch chuyển động.
Các thuật toán lập kế hoạch chuyển động dựa trên mẫu thường tạo ra và sắp xếp một tập các chuyển động của
ứng viên quỹ đạo để tạo ra một quỹ đạo tối ưu. Trong hình 1, có thể thấy phương tiện tự hành có thể hoạt động giữ làn
đường hoặc thay đổi làn đường khi tùy thuộc vào bộ ứng viên chuyển động. Để có bộ ứng viên chuyển động như hình
1, các thuật toán lập kế hoạch chuyển động dựa trên mẫu sẽ thực hiện các bước cơ bản sau [10]:
Bảng 1. Minh họa phương án lập kế hoạch chuyển động dựa trên mẫu
Algorithm: Lập kế hoạch chuyển động dựa trên lấy mẫu
Input: tập ứng viên quỹ đạo
Output: Xopt(t) là quỹ đạo tối ưu
Begin
1 Khởi tạo mục tiêu chuyển động( ) (sg,ng);
2 for i =1 to N do
3 Tạo ứng viên quỹ đạo(sg,ng) Xi(t);
4 Tính chi phí quỹ đạo(Xi(t)) ci;
5 end
6 Chọn quỹ đạo tối ưu (X(t),c) Xopt(t);
End
- Khởi tạo tập các mục tiêu chuyển động được chọn trong không gian mẫu.
- Xây dựng các quỹ đạo dựa trên bộ mục tiêu chuyển động, bằng cách kết nối từ vị trí xe hiện tại đến các mục
tiêu chuyển động, các kết nối này được thực hiện dựa trên mô hình xe và các ràng buộc non-holonomic.
- Mỗi quỹ đạo được đánh giá định lượng bằng cách sử dụng dữ liệu tri giác thu nhận được từ môi trường và các
hàm chi phí liên quan đến các chỉ số hoạt động khác nhau (độ an toàn, độ giật của xe khi di chuyển và vị trí trung tâm
của làn đường); quá trình tính toán định lượng các quỹ đạo được thực hiện với tất cả các quỹ đạo.
- Xác định quỹ đạo tối ưu có các chi phí tối thiểu để thực hiện kế hoạch chuyển động của xe.
Bốn thao tác cơ bản này hoạt động lặp lại đến lúc tìm được quỹ đạo tối ưu trong thuật toán lập kế hoạch dựa
trên mẫu để xây dựng được đường đi đảm bảo an toàn và tối ưu.
Khi có nhiều mẫu trong quá trình lặp của bài toán thì chúng cần được bảo đảm sẽ bao quát một không gian tìm
kiếm lớn để tìm ra quỹ đạo, trong khi khối lượng tính toán tăng lên nhanh chóng bằng cách tăng số lượng mẫu N. Vì
vậy, các mẫu nên được quản lý không chỉ để tìm ra quỹ đạo tối ưu mà còn để cải thiện hiệu suất tính toán.
Lọc là bài toán đóng vai trò quan trọng trong lĩnh vực xử lý tín hiệu, bài toán này giải quyết triệt để vấn đề ước
lượng trạng thái của một hệ thống khi một tập quan sát về hệ thống đó được thu thập và có hiệu lực. Nhưng các hệ
- Quách Hải Thọ, Huỳnh Công Pháp, Phạm Anh Phương 283
thống thu thập trên thực tế là phi tuyến và có nhiều loại nhiễu trên phép đo. Để ước lượng trạng thái các hệ thống trên
ta sử dụng bộ lọc phần tử hay phương pháp Sequential Monte Carlo (SMC) [19].
Hiện nay trên thế giới, bộ lọc phần tử đang được áp dụng rộng rãi trong nhiều lĩnh vực khoa học công nghệ như
giao thông, an ninh quốc phòng, thị giác robot, di động không dây ... Trong đó các thuật toán bộ lọc phần tử đã được
cải tiến liên tục nhằm đáp ứng các yêu cầu thực tế và có một vài nghiên cứu về bộ lọc phần tử thực hiện trên phần
cứng.
2.1. Bộ lọc phần tử
Bộ lọc phần tử (hay có tên khác là bộ lọc chất điểm, bộ lọc Boostrap, bộ lọc Monte Carlo đều dựa trên nền tảng
của phương pháp Monte Carlo) [19] đây là thuật toán dùng để ước lượng trực tiếp các mật độ hậu nghiệm của mô hình
không gian trạng thái bằng cách triển khai thực hiện phương trình đệ quy Bayes. Mô hình không gian trạng thái có thể
phi tuyến và phân bố nhiễu dưới bất kỳ hình thức nào, phương trình đệ quy Bayes sử dụng một phương pháp tiếp cận
dựa trên quần thể. Các mẫu phân phối được thể hiện bằng một tập hợp các phần tử, mỗi phần tử được gán một trọng
lượng đại diện cho xác suất phần tử được lấy mẫu từ hàm mật độ xác suất. Sự chênh lệch của các trọng lượng dẫn đến
sự thoái hóa trọng lượng là một vấn đề thường gặp trong các thuật toán lọc. Tuy nhiên, có thể giảm thiểu bằng phương
pháp tái chọn mẫu; trong bước tái chọn mẫu các phần tử có trọng lượng không đáng kể được thay thế bằng các phần tử
lân cận được tạo ra từ các phần tử có trọng lượng lớn hơn.
Quá trình lọc phần tử gồm các bước sau đây [15]:
1. Khởi tạo: Trong xác định trạng thái sử dụng bộ lọc phần tử, có phần tử [ ] ban đầu được khởi tạo
ngẫu nhiên dựa trên hàm mật độ xác suất của trạng thái ban đầu ( ̂ ) (được giả định là không biết). Số các phần tử
được xem là hệ số an toàn để xác định hiệu quả tính toán và độ chính xác trong việc xác định trạng thái.
2. Cập nhật thời gian: Sử dụng mô hình hệ thống và các đặc trưng nhiễu của trạng thái trước, các phần tử ưu tiên
được tính như sau: ( ) ( ) (1)
3. Cập nhật theo giá trị đo lường: Trọng lượng của mỗi phần tử được cập nhật trên cơ sở của cảm biến đo
lường . Điều này được thực hiện bằng hàm hợp lý (likehood function) ( ) trên cơ sở phương trình phi tuyến
và hàm mật độ xác suất của nhiễu cảm biến. Ngoài ra, trọng lượng thu được cũng chuẩn hóa như sau: ∑
4. Xác định trạng thái: Sử dụng tập các phần tử và trọng lượng , các phần tử sau có thể tính xấp xỉ bằng
∑ (2)
5. Tái chọn mẫu: Để tạo ra một tập mới gồm các phần tử là các mẫu ngẫu nhiên được chọn lựa trên cơ sở
các trọng số. Việc tái chọn mẫu nhằm ngăn sự tập trung xác suất rơi vào một vài phần tử và quản lý hiệu quả một số
lượng giới hạn các phần tử để xác định các trạng thái được chính xác.
Điểm mấu chốt của quá trình lọc phần tử là việc quản lý các phần tử với hàm xác suất hợp lý, bộ lọc phần tử
giải quyết vấn đề bằng cách tạo ra một tập mẫu để ước lượng. Tập mẫu càng lớn, việc ước lượng càng chính xác nhưng
khối lượng tính toán sẽ tăng cao. Bộ lọc phần tử sẽ ước lượng trạng thái kế tiếp của hệ thống bằng cách lấy trạng thái
trước đó, tạo ra Nmẫu phần tử, mỗi mẫu phần tử sẽ được ước lượng (điều kiện không nhiễu) bằng cách nhân từng phần
tử với trọng số riêng và tính tổng lại để ra trạng thái ước lượng kế tiếp. Các trọng số riêng này sẽ được cập nhật bằng
cách sử dụng quan sát ở thời điểm đó theo xác suất Bayes. Bộ lọc phần tử được thiết kế cho các hệ thống phi tuyến nên
lược đồ tối ưu hóa xác suất có thể được mở rộng cho các ứng dụng phi tuyến khác và là một công cụ hữu ích trong việc
ước lượng và dự đoán trạng thái của đối tượng.
2.2. Giải pháp lập kế hoạch chuyển động
Kiến trúc tổng thể của một hệ thống lái tự động cho xe tự hành, bao gồm các module sau: Module bản đồ định vị
sẽ cung cấp vị trí của xe trên hệ thống toàn cục, dữ liệu tri giác sẽ cung cấp thông tin về các chướng ngại vật phát hiện
được; dựa trên thông tin dữ liệu tri giác và định vị, module lập kế hoạch chuyển động sẽ tạo ra một quỹ đạo mục tiêu và
sau đó module điều khiển sẽ chuyển lệnh để các bộ chuyển động thực hiện điều khiển xe theo quỹ đạo đã tìm ra.
Hình 2. Kiến trúc tổng thể của hệ thống lái tự động cho xe tự hành
- 284 MỘT GIẢI PHÁP KỸ THUẬT THIẾT LẬP KẾ HOẠCH CHUYỂN ĐỘNG CHO XE TỰ HÀNH
Giải pháp lập kế hoạch chuyển động mà chúng tôi đề xuất này được thực hiện dựa trên kỹ thuật lấy mẫu, nên
các ứng viên quỹ đạo được quản lý lặp đi lặp lại để tạo ra quỹ đạo; để quản lý các ứng viên hiệu quả thì quy trình lọc
phần tử được áp dụng trong quy hoạch chuyển động này cần sử dụng 4 bước chính: cập nhật thời gian ứng viên, cập
nhật dữ liệu tri giác, lựa chọn quỹ đạo và tái lấy mẫu mục tiêu chuyển động.
Trong 4 bước này thì cập nhật thời gian của ứng viên quỹ đạo và cập nhật dữ liệu tri giác được thiết kế để xét
tính không chắc chắn của dữ liệu định vị và dữ liệu tri giác trong quá trình lập kế hoạch chuyển động. Ngoài ra, bước
tái lấy mẫu mục tiêu chuyển động nhằm cải thiện hiệu suất tính toán bằng cách quản lý các mục tiêu chuyển động của
các ứng viên quỹ đạo.
Giải pháp chúng tôi đề xuất hoạt động đệ quy và dựa trên phương pháp lọc phần tử nên quỹ đạo cuối cùng của các
ứng viên được chọn bởi các lược đồ tối ưu xác suất; và các bước cập nhật thời gian của ứng viên quỹ đạo sẽ khởi tạo cập nhật
các mục tiêu chuyển động bằng dữ liệu định vị và các mô hình xe, đồng thời sẽ khởi tạo một tập các ứng viên quỹ đạo mới.
Trong bước cập nhật dữ liệu tri giác, trọng số của mỗi quỹ đạo được tính bằng cách sử dụng dữ liệu tri giác và hàm hợp lý
thích ứng; bước lựa chọn quỹ đạo tiếp theo sẽ chọn một quỹ đạo tối ưu từ các ứng viên dựa trên yếu tố trọng số; bước cuối
cùng là tái lấy mẫu mục tiêu chuyển động sẽ thay đổi tập các mục tiêu chuyển động dựa trên trọng số.
2.2.1. Khởi tạo
Khởi tạo mục tiêu chuyển động ban đầu ( ) và trọng số của các ứng viên quỹ đạo được thiết lập theo giá
trị của các ứng viên quỹ đạo là giá trị có yếu tố quan trọng tác động đến hiệu năng tính toán trong phương pháp lập
kế hoạch dựa trên mẫu; Do đó, việc xem xét để đưa ra một số của các ứng viên quỹ đạo thích hợp là vấn đề mà các
giải pháp tính toán trong lập kế hoạch chuyển động phải tính đến.
Với giá trị của các ứng viên quỹ đạo, các mục tiêu chuyển động ban đầu ( ) được thống nhất chọn dọc
theo trục thẳng của xe và trọng số của mỗi quỹ đạo sẽ được khởi tạo như sau: ⁄
Hình 3. Tập ứng viên quỹ đạo và mục tiêu chuyển động
2.2.2. Cập nhật thời gian của ứng viên quỹ đạo
Thực hiện tương tự như cập nhật thời gian trong hoạt động của bộ lọc phần tử. Tuy nhiên, bản cập nhật thời
gian của các ứng viên quỹ đạo được thực hiện với mô hình hệ thống được thiết kế dành cho chuyển động của xe là:
( )
[ ] [ ] [ ] (3)
( )
Trong đó: [ ] là vị trí xe được xác định trong hệ tọa độ Descartes, là khoảng thời gian cập nhật của hệ
thống, là vận tốc và là góc đảo lái thu được từ hệ thống định vị. Trên cơ sở của mô hình hệ thống thiết kế, các mục
tiêu chuyển động được cập nhật lại như sau:
( )
[ ] [ ] ( )[ ] (4)
( )
Trong đó: [ ] là vị trí mục tiêu chuyển động thứ i được xác định trong hệ tọa độ Descartes, là cảm biến
nhiễu của từng mục tiêu chuyển động cho góc đảo lái. Do đó, việc phân phối các mục tiêu chuyển động cập nhật có thể
thay đổi theo các đặc tính của cảm biến nhiễu và trong hệ thống định vị.
Các ứng viên quỹ đạo là tập bao gồm đường dẫn và thông tin chuyển động được cập nhật để kết nối từ vị trí xe
đến từng mục tiêu chuyển động; vì thông tin đường dẫn gồm vị trí ( ), góc và độ cong của ứng viên quỹ đạo là
biểu diễn chuyển động của xe dọc theo đường.
Hình 4. Minh họa cập nhật thời gian của ứng viên quỹ đạo sử dụng thông tin định vị
- Quách Hải Thọ, Huỳnh Công Pháp, Phạm Anh Phương 285
Cả 2 hệ thống tọa độ là tọa độ Descartes ( ) và tọa độ đường thẳng ( ) được sử dụng đồng thời, mối quan
hệ giữa 2 hệ thống tọa độ này được biểu diễn và chuyển đổi qua tọa độ cong bởi ánh xạ: ( ) ( ); trong các
tọa độ đường thẳng ( ), thông tin đường dẫn có thể được biểu diễn lại bằng cách sử dụng hàm đa thức bậc 3 như
sau:
( ) { (5)
Trong đó là sự khác biệt giữa mục tiêu chuyển động và vị trí của xe theo chiều dọc; , , và là các
hệ số của ứng viên quỹ đạo thứ i, có thể được xác định bằng các điều kiện biên như sau:
( ) và ( ) ( ) (6)
( ) và ( ) (7)
Thông tin chuyển động không cố định của các ứng viên quỹ đạo bao gồm dữ liệu thời gian như thời gian , vận
tốc , gia tốc và giá trị biến thiên độ cong có thể được xác định trên cơ sở của dữ liệu giới hạn tốc độ tối thiểu từ
nhiều nguồn khác nhau (như giới hạn tốc độ của hệ thống điều khiển hành trình, giới hạn tốc độ dựa trên gia tốc
ngang trong đường cong và giới hạn tốc độ tối đa trong hệ thống giao thông) như trong hình 5 và phương trình sau:
( ) trong đó ( ), √ và ( ) (8)
Hình 5. Minh họa thông tin giới hạn tốc độ của kế hoạch chuyển động không cố định
Dựa trên thông tin giới hạn tốc độ, hệ thống gia tốc được dẫn xuất bằng cách áp dụng mô hình gia tốc không đổi
giữa các nút trong mỗi ứng viên quỹ đạo như trong hình 6 và các giá trị được tính bởi phương trình sau:
( ) ( )
và
trong đó là sự khác nhau về khoảng cách giữa 2 nút trong một ứng viên quỹ đạo.
Hình 6. Mô hình gia tốc không đổi
Kết quả cuối cùng, sẽ thu được là các ứng viên quỹ đạo có thể bao gồm một tập các nút quỹ đạo được cập nhật
và thông tin chuyển động không cố định.
2.2.3. Cập nhật đo lường dữ liệu tri giác
Để xe tự hành có thể chuyển động theo đúng hướng và tránh được chướng ngại vật, thì dữ liệu tri giác như cấu
trúc đường thực tế và trạng thái các chướng ngại vật phải được xét đến khi lựa chọn quỹ đạo. Tuy nhiên, do nhiễu và
bất định trong các phép đo trên mỗi cảm biến nên hầu hết các thuật toán thị giác dựa trên kỹ thuật ước tính xác suất
như bộ lọc Kalman hoặc Kalman mở rộng đều cung cấp sai số hiệp phương sai để biểu thị độ chính xác xác suất [3, 6,
9]. Để ứng dụng thông tin xác suất trong lựa chọn quỹ đạo, trọng số của mỗi quỹ đạo được tính trên cơ sở của trường
khả năng thích ứng [17]; trường khả năng thích ứng mô tả phân bố thích ứng cho dữ liệu đo lường trong không gian đo
lường.
- 286 MỘT GIẢI PHÁP KỸ THUẬT THIẾT LẬP KẾ HOẠCH CHUYỂN ĐỘNG CHO XE TỰ HÀNH
Về cơ bản, khi xe tự hành di chuyển sẽ thực hiện các chức năng giữ làn đường và thay đổi làn đường. Để tăng
trọng số cho mỗi ứng viên quỹ đạo nằm ở trong làn đường thì yếu tố hình học của đường với khả năng thích ứng
được định nghĩa như sau:
| |
( ) | |
( ) | | (9)
( ) | |
{ | |
trong đó là vị trí bên của nút quỹ đạo thứ j; là vị trí bên của làn đường đích; là vị trí bên của làn thứ khác;
là vị trí bên của ranh giới đường, là phân phối xác suất mục tiêu; là phân phối xác suất của làn thứ khác.
Để tránh được chướng ngại vật một cách an toàn, xe tự hành cần phải phát hiện chính xác những chướng ngại
vật cả tĩnh và động; để thực hiện tốt vấn đề này các thiết bị cảm biến như quét laze, radar sẽ được lắp đặt đầy đủ trên xe
[11]. Trong bài báo này, chúng tôi giả định rằng hệ thống tri giác cung cấp cho hệ thống xử lý bản đồ chướng ngại vật
tĩnh và danh sách các chướng ngại vật động từ dữ liệu đo lường của các thiết bị cảm biến.
Bản đồ lưới thể hiện môi trường đã chia nhỏ thành các mắt lưới được sử dụng để xây dựng bản đồ chướng ngại
vật tĩnh [18]; vì mỗi ô có xác suất ước tính hiện ô có bị chiếm giữ hay không. Bản đồ lưới có thể chuyển đổi trực tiếp
thành chướng ngại vật tĩnh với trường khả năng thích ứng sử dụng phép tích chập Gauss như sau:
( ) ( ) ( ) trong đó ( ) ( ) (10)
với là giá trị đại diện cho mức độ an toàn trong một ô và do đó nếu giá trị này thấp có nghĩa là có một chướng ngại
vật trong ô; là đặc tính nhiễu của cảm biến được phản ánh bằng cách áp dụng phép biến đổi Gauss với bản đồ lưới.
Cũng giống như chướng ngại vật tĩnh, chướng ngại vật động được tính với trường khả năng thích ứng đại
diện cho xác suất liên quan đến mức độ an toàn trên đường. Tuy nhiên, do vị trí của chướng ngại vật động thay đổi
theo thời gian, nên dự đoán chuyển động sử dụng thông tin trạng thái của danh sách chướng ngại vật động để ước
lượng tránh va chạm và đảm bảo an toàn.
( ) ( ) ( ) (11)
trong đó ( ) ( ) và ( )
với là phép tích chập Gauss; là giá trị đại diện cho trạng thái dự đoán của các chướng ngại vật động.
So với thì ngoài việc xét đến đặc tính nhiễu của cảm biến mà còn tính đến lỗi mô hình trong dự đoán
chuyển động ở tương lai. Giá trị hiệp phương sai thay đổi theo thời gian dự đoán t và vận tốc tương đối , cũng
như hiệp phương sai của cảm biến cơ sở .
Vì các phép đo lường tri giác độc lập nhau, nên việc tích hợp các trường khả năng thích ứng có thể được thực
hiện như sau:
( ) ∏ ( ) ( ) ( ) ( ) (12)
Trên cơ sở này, trọng số của các ứng viên quỹ đạo có thể được cập nhật; vì trọng số của mỗi nút khác trong
ứng viên quỹ đạo cũng độc lập, trọng số của ứng viên quỹ đạo thứ i tại bước thời gian là được xác định bằng cách
nhân trọng số của tất cả các nút bằng quá trình chuẩn hóa:
∏ ( ) và ̂ ∑ (13)
2.2.4. Lựa chọn quỹ đạo
Việc lựa chọn quỹ đạo được thực hiện dựa trên trọng số cập nhật của các ứng viên quỹ đạo, quỹ đạo cuối cùng
tại bước thời gian k được chọn trong bước lựa chọn quỹ đạo. Để chọn được quỹ đạo tối ưu, chúng ta tìm giá trị cực
đại của phương pháp đánh giá quy nạp: [ ̂ ( )] (14)
trong đó arg max là hàm để tìm ứng viên quỹ đạo của miền ̂ mà tại đó giá trị đạt cực đại.
2.2.5. Tái lấy mẫu mục tiêu chuyển động
Với mục đích ngăn sự tập trung của quá trình cập nhật trọng số sẽ rơi vào một vài ứng viên quỹ đạo và quản lý
hiệu quả số lượng ứng viên hạn chế để tìm được quỹ đạo tối ưu, thì việc tái lấy mẫu mục tiêu chuyển động nhằm tái tạo
một tập mới các mục tiêu chuyển động cho các ứng viên quỹ đạo trên cơ sở trọng số là cần thiết.
- Quách Hải Thọ, Huỳnh Công Pháp, Phạm Anh Phương 287
Bước tái lấy mẫu mục tiêu chuyển động này được thực hiện nếu thỏa mãn điều kiện
∑ ( )
[32]; trong đó là số ứng viên hiệu dụng, đại diện cho mức độ tập trung của trọng số; là tỷ lệ ngưỡng và là một
yếu tố được thiết kế để sử dụng cho việc xác định tần suất của hoạt động tái lấy mẫu.
Nếu việc tái lấy mẫu được xác định, thì có 2 loại mục tiêu chuyển động được tái tạo: mục tiêu chuyển động cố
định và mục tiêu chuyển động ngẫu nhiên. Để kiểm tra độ an toàn của tất cả các làn đường, mục tiêu chuyển động cố
định được tạo ra ở trung tâm của mỗi làn đường và có rất ít mục tiêu chuyển động được tái tạo thành mục tiêu chuyển
động cố định; mà hầu hết các mục tiêu chuyển động được tái tạo bằng cách áp dụng kỹ thuật lấy mẫu có phương sai
thấp dựa trên trọng số của các ứng viên quỹ đạo, kỹ thuật này có độ phức tạp tính toán thấp và độ phủ không gian tốt
của không gian mẫu [19].
III. ĐÁNH GIÁ VÀ KẾT LUẬN
Giải pháp lập kế hoạch chuyển động đề xuất dựa trên thiết kế của bộ lọc phần tử đối với bài toán xe tự hành
được thực nghiệm mô phỏng với nhiều tình huống giao thông khác nhau. Quá trình quy hoạch chuyển động này được
thực hiện dựa trên kỹ thuật lấy mẫu ngẫu nhiên, các trường hợp thực nghiệm giống nhau cũng có thể cho các kết quả
khác nhau. Để đánh giá hiệu suất của giải pháp này, chúng tôi áp dụng phương pháp mô phỏng Monte Carlo [34] với
một kịch bản thử nghiệm được lặp lại nhiều lần; và thực hiện đồng thời với phương pháp lập kế hoạch chuyển động
bằng kỹ thuật cây RRT; kịch bản thử nghiệm được áp dụng giống nhau cho cả 2 phương pháp.
Trong mô phỏng, giải pháp chúng tôi đề xuất sử dụng 60 ứng viên quỹ đạo và phương pháp sử dụng kỹ thuật
cây RRT sử dụng 200 ứng viên quỹ đạo để tìm ra quỹ đạo tối ưu.
Để đánh giá định lượng cho giải pháp đề xuất, chúng tôi đã phân tích thời gian tính toán và tỷ lệ thất bại như
trong bảng 2; trong phân tích này, chúng tôi thực hiện 5 kịch bản thử nghiệm được áp dụng bằng các chướng ngại vật
khác nhau, mỗi kịch bản thử nghiệm 50 lần cho các mô phòng Monte Carlo, nếu quỹ đạo đã chọn gây ra va chạm trong
quá trình mô phòng thì trường hợp thử nghiệm này được đánh dấu là trường hợp lỗi.
Bảng 2. So sánh thời gian xử lý và tỷ lệ thất bại với số lượng ứng cử viên quỹ đạo
Số lượng ứng viên Thời gian xử lý (ms) Tỷ lệ thất bại (%)
10 22.85 10.8
50 27.40 1.0
Giải pháp đề xuất 100 40.20 0
200 60.28 0
500 145.20 0
10 21.00 40.2
50 25.80 15.4
Giải pháp dùng để đánh giá 100 38.40 2.6
200 58.70 0.8
500 120.10 0
Như trong bảng 2, thời gian thực hiện của giải pháp đề xuất lớn hơn so với giải pháp sử dụng cây RRT cho cùng
số lượng ứng viên; lý do là vì phương pháp này cần cập nhật thời gian lập kế hoạch quỹ đạo và tái lấy mẫu chuyển
động cục bộ. Tuy nhiên, hiệu suất an toàn của giải pháp này là cao hơn, đồng thời giải pháp này có tỉ lệ thất bại thấp
hơn mặc dù số lượng ứng viên nhỏ là do giải pháp này lặp đi lặp lại quá trình thay đổi mục tiêu chuyển động có sử
dụng trọng số.
Kết quả đánh giá về điều kiện an toàn thì giải pháp đề xuất đã đạt được hiệu quả và phương pháp lập kế hoạch
chuyển động này đã tạo ra một quỹ đạo tối ưu cho phép một xe tự hành có thể lái dọc theo đường và tránh chướng ngại
vật an toàn. Để nâng cao hiệu quả tính toán và xem xét xác suất không chắc chắn của dữ liệu tri giác và định vị trên
quỹ đạo tổng quát; thì hiệu suất của giải pháp đề xuất này còn phụ thuộc vào mô hình xác suất của hệ thống để tạo ra
các trường khả năng thích ứng. Do đó, phân tích xác suất và phương pháp biểu diễn tình huống lái xe cần được tích
hợp nhiều hơn đối với việc áp dụng vào xe thực tế.
IV. TÀI LIỆU THAM KHẢO
[1] Bevan, Gollee and O’Reilly. Trajectory generation for road vehicle obstacle avoidance using convex optimization.
Proc IMechE Part D: J Automobile Engineering, pp.455-473, 2010.
[2] Brannstrom M., Sandblom F. and Hammarstrand L.. A probabilistic framework for decision-making in collision
avoidance systems. IEEE Trans Intell Transpn Systems, pp.637-648, 2013.
[3] Dongchul K, Jaehyun H. and Myoungho S.. Multiple vehicle tracking in urban environment using integrated
probabilistic data association filter with single laser scanner. Trans KSAE, pp.33-42, 2013.
- 288 MỘT GIẢI PHÁP KỸ THUẬT THIẾT LẬP KẾ HOẠCH CHUYỂN ĐỘNG CHO XE TỰ HÀNH
[4] Eidehall A. and Petersson L.. Statistical threat assessment for general road scenes using Monte Carlo sampling.
IEEE Trans Intell Transpn Systems, pp.137-147, 2008.
[5] Fraichard and Howard. Iterative motion planning and safety issue. In: Eskandarian A (ed) Handbook of intelligent
vehicles. London: Springer, pp. 1433-1458, 2012.
[6] Han J., Kim D., Lee M. and Sunwoo M.. Enhanced road boundary and obstacle detection using a downward
looking LIDAR sensor. IEEE Trans Veh Technol, pp.971-985, 2012.
[7] Laugier C., Paromtchik I. E., Perrollaz M. et al.. Probabilistic analysis of dynamic scenes and collision risks
assessment to improve driving safety. IEEE Intell Transpn Systems Mag, pp.4-19, 2011.
[8] Ibanez-Guzman, Laugier and Thrun S.. Autonomous driving: context and state-of-the-art, In:Eskandarian A (ed)
Handbook of intelligent vehicles. London: Springer, pp.1271-1310, 2012.
[9] Jo K., Chu K. and Sunwoo M.. Interacting multiple model filter-based sensor fusion of GPS with in-vehicle sensors
for real-time vehicle positioning. IEEE Trans Intell Transpn Systems, pp.329-343, 2012.
[10] Jo K. and Sunwoo M.. Generation of a precise roadway map for autonomous cars. IEEE Trans Intell Transpn
Systems, pp.925-937, 2014.
[11] Jo K., Kim J., Kim D. et al.. Development of autonomous car - Part I: distributed system architecture and
development process. IEEE Trans Ind Electron, pp.7131-7140, 2014.
[12] Kim J., Jo K., Chu K. and Sunwoo M.. Road-modelbased and graph-structure-based hierarchical path planning
approach for autonomous vehicles. Proc IMechE Part D: J Automobile Engineering, pp.909-228, 2014.
[13] Kim J., Jo K., Lim W. et al.. Curvilinear-coordinate-based object and situation assessment for highly automated
vehicles. IEEE Trans Intell Transpn Systems, pp.1559-1575, 2015.
[14] Shim T., Adireddy G. and Yuan H.. Autonomous vehicle collision avoidance system using path planning and
model-predictive-control-based active front steering and wheel torque control. Proc IMechE Part D: J
Automobile Engineering, pp.767-778, 2012.
[15] Simon D.. Optimal state estimation: Kalman, HN, and nonlinear approaches. New York: John Wiley, 2006.
[16] Su J. L. and Ordys A.W.. Collision avoidance manoeuvre for a vehicle - a practical approach. Proc IMechE Part
D: J Automobile Engineering, pp.299-312, 2010.
[17] Schubert R. and Wanielik G.. A unified Bayesian approach for object and situation assessment. IEEE Intell
Transpn Systems Mag, pp.6-19, 2011.
[18] Suganuma N. and Matsui T.. Robust environment perception based on occupancy grid maps for autonomous
vehicle. In: 2010 SICE annual conference, Taipei, Republic of China, pp. 2354-2357, 2010.
[19] Thrun S., Burgard W. and Fox D.. Probabilistic robotics. Cambridge, Massachusetts: MIT Press, 2005.
[20] Zhang D., Li K. and Wang J.. Radar-based target identification and tracking on a curved road. Proc IMechE Part
D: J Automobile Engineering, pp.39-47, 2012.
A TECHNICAL SOLUTION CREATING MOTION PLANNING FOR AUTONOMOUS
VEHICLES
Quach Hai Tho, Huynh Cong Phap, Pham Anh Phuong
ABSTRACT: Using a sampling-based approach, to create the optimal trajectory from the set of trajectory candidates aiming at
improving performance and enhancing motion planning capabilities based on the information received fromthe transport
infrastructure system and other objects on the road through the sensor system, in this paper, to handle the uncertainty in the sensory
data and vehicle system structure, we propose a motion planning solution for autonomous vehicles that uses the basic structure of
the particle filter with four basic steps repeated until the optimal trajectory is found, then we evaluate the solution and apply the
problem of autonomous vehicles in real life.
Keywords: Autonomous vehicle, particle filter, path planning, motion planning, intelligent transportation systems.
nguon tai.lieu . vn
