Thuật toán làm mịn đường dẫn Python

Một phương pháp khác để làm trơn là đường trung bình động. Có nhiều hình thức khác nhau, nhưng ý tưởng là lấy một cửa sổ các điểm trong tập dữ liệu của bạn, tính trung bình các điểm, sau đó dịch chuyển cửa sổ qua một điểm và lặp lại. Điều này sẽ tạo ra một loạt các điểm dẫn đến dữ liệu smoothed

Trước tiên chúng ta hãy nhìn vào Simple Moving Average chung. Trong trường hợp 1D, chúng tôi có tập dữ liệu gồm $N$ điểm với các giá trị y $y_1, y_2,. , y_N$. Đặt kích thước cửa sổ của chúng ta thành $n < N$, giá trị $i^{th}$ y mới sau khi làm mịn được tính là

$$ \begin{align*} SMA_i = \frac{y_i +. + y_{i+n}}{n} \end{align*} $$

Trong Triangular Moving Average, hai đường trung bình động đơn giản được tính chồng lên nhau, để tăng thêm trọng lượng cho các điểm gần hơn [liền kề]. Điều này có nghĩa là $SMA_i$ của chúng tôi được tính toán thì Đường trung bình động tam giác $TMA_i$ được tính như sau

Đây là một phần của loạt bài viết liên quan đến làm việc thông qua khóa học AI cho Robotics trên Udacity. Bài viết này là về Bài học 5

Trong các môi trường rời rạc, chẳng hạn như thế giới lưới, các vấn đề về đường đi ngắn nhất được giải quyết bằng cách sử dụng thuật toán tìm số vị trí lưới tối thiểu cần thiết để di chuyển từ vị trí bắt đầu đến vị trí cuối

Điều này hoạt động tốt cho các đối tượng, chẳng hạn như hình vuông do người dùng điều khiển trong thế giới 2 chiều, có thể chắc chắn đi từ vị trí này sang vị trí khác mà không phải lo lắng về các hạn chế trong chuyển động

Giả sử chúng ta bắt đầu với ô màu Vàng ở vị trí bắt đầu. Có nhiều giải pháp cho lưới này nhưng mục đích là để chỉ ra rằng đối tượng của chúng ta không gặp vấn đề gì khi di chuyển từ ô lưới này sang ô lưới tiếp theo

Đây không phải là trường hợp cho xe cộ. Hoàn toàn có khả năng một thuật toán lập kế hoạch cung cấp cách hiệu quả nhất để đến đích theo các đường thẳng hoàn toàn, như minh họa bên dưới

Các giải pháp lập kế hoạch đơn giản được tối ưu hóa cho các đối tượng có thể điều hướng thế giới lưới theo đường thẳng

Lập kế hoạch rẽ cong sẽ là một giải pháp lý tưởng cho xe buýt do thực tế là nó không thể rẽ 90 độ ngay tại chỗ. Một lý do bổ sung để làm mịn là cho phép giải phóng mặt bằng để cho phép lỗi xảy ra một cách tự nhiên trong quá trình chuyển động. Có thể có một lỗi nhỏ trong dữ liệu cảm giác xác định vị trí của phương tiện và bản thân hành động di chuyển có khả năng tích lũy một số lỗi

Đường cong quỹ đạo

Giả sử chúng ta đã có một con đường tối ưu cho ô tô đi, nhưng chúng ta muốn làm phẳng quỹ đạo. Đối với các phương trình này, y đại diện cho một tọa độ được làm mịn ở bước thời gian i trong khi x đại diện cho tọa độ ban đầu không được làm mịn. Phần tử thứ i của x đề cập đến một danh sách chứa tọa độ x và y của một đối tượng tại bước thời gian thứ i

Các tọa độ đường dẫn unsmooth

Các tọa độ đường dẫn mịn

Chúng tôi khởi tạo y_i thành x_i trước khi thực hiện quy trình lặp lại để điều chỉnh đường dẫn được làm mịn dựa trên các bước tối ưu hóa

Khởi tạo y là x, đường dẫn không trơn

Tối ưu hóa đầu tiên là giảm thiểu khoảng cách giữa tọa độ của đường dẫn ban đầu [x] và đường dẫn được làm mịn [y]

Giảm thiểu khoảng cách giữa đường dẫn ban đầu và đường dẫn được làm mịn

Sau đó, trong cùng một lần lặp lại, chúng ta cần giảm thiểu sự khác biệt giữa tọa độ của đường được làm nhẵn ở bước thời gian i và các bước thời gian liền kề. Điều này sẽ không hoạt động đối với bước cuối cùng, vì có rất nhiều bước liên tiếp vượt qua nó, nhưng điều này có thể chấp nhận được vì chúng ta không nên làm trơn bước cuối cùng [cũng như bước thời gian ban đầu]

Nếu chúng ta chỉ giảm thiểu khoảng cách giữa đường không trơn và đường trơn, thì cuối cùng chúng ta sẽ không thay đổi được đường trơn. Điều này là do kết quả của phương trình sẽ luôn bằng không. Giảm thiểu số không sẽ không thay đổi bất cứ điều gì

Mặt khác, nếu chúng ta chỉ thu nhỏ khoảng cách giữa hai điểm nhẵn liên tiếp, thì cuối cùng bạn sẽ không có đường đi nào cả. Điều này là do các điểm ở giữa bước đầu tiên và bước cuối cùng sẽ được thu nhỏ thành một điểm duy nhất

Vì hai tối ưu hóa theo một số cách xung đột với nhau, bạn có thể điều chỉnh tầm quan trọng của tối ưu hóa làm mịn bằng siêu tham số alpha. Alpha càng cao, tọa độ càng được làm mịn, trong khi ngược lại sẽ dẫn đến tọa độ có độ bám dính cao hơn với tập hợp tọa độ không được làm mịn ban đầu

Alpha điều chỉnh tầm quan trọng của đầu ra làm mịn

Để giảm thiểu cả hai điều khoản, chúng ta có thể sử dụng Gradient Ascent. Trong video, Sebastian nói về việc sử dụng Gradient Descent [điều này có ý nghĩa với tôi vì đã sử dụng nó rộng rãi trong nhiều Deep Networks]. Tuy nhiên, trong giải pháp, trợ giảng khuyên chúng tôi sử dụng Gradient Ascent để thuật toán hội tụ, điều này khiến tôi tin rằng hàm lỗi phải lồi

Đối với lần cập nhật đầu tiên, chúng tôi có thể cập nhật tọa độ được làm trơn theo hướng giảm thiểu khoảng cách giữa tọa độ không được làm trơn và tọa độ được làm trơn

Bản cập nhật Gradient Ascent cho y_i đối với quỹ đạo không được làm phẳng

Đối với lần cập nhật thứ hai, chúng tôi có thể cập nhật các tọa độ được làm mịn theo hướng giảm thiểu độ lệch giữa các tọa độ được làm mịn liền kề. Beta hoạt động giống như alpha ở chỗ điều chỉnh mức độ nhấn mạnh vào bản cập nhật tọa độ được làm mịn

Cập nhật Gradient Ascent cho y_i đối với các tọa độ được làm mịn lân cận

Khi triển khai bản cập nhật này, điều quan trọng là phải cập nhật y_i trong một bước vì cả hai thuật ngữ lỗi đều phụ thuộc vào y_i. Cập nhật cái này trước cái kia [như được đề xuất bởi Sebastian] sẽ dẫn đến thuật ngữ lỗi thứ hai cập nhật một y_i khác

Mã giải pháp

# Coordinate Updates:
[0.000, 0.000] -> [0.000, 0.000]
[0.000, 1.000] -> [0.021, 0.979]
[0.000, 2.000] -> [0.149, 1.851]
[1.000, 2.000] -> [1.021, 1.979]
[2.000, 2.000] -> [2.000, 2.000]
[3.000, 2.000] -> [2.979, 2.021]
[4.000, 2.000] -> [3.851, 2.149]
[4.000, 3.000] -> [3.979, 3.021]
[4.000, 4.000] -> [4.000, 4.000]

Tôi đã cấu trúc lại mã của mình [có giải pháp chính xác] thành mã giải pháp Udacity một cách cụ thể bởi vì mặc dù giải pháp của tôi có thể nhận được đầu ra chính xác, nhưng nó không phải là mô-đun cho đa chiều. Nói cách khác, nếu danh sách đầu vào chứa các mục không phải là hai chiều, thì mã của tôi sẽ bị hỏng

Để đảm bảo rằng tôi không cập nhật tọa độ đầu tiên và cuối cùng, ban đầu tôi đã sử dụng liệt kê và điều kiện để xem vị trí chỉ mục của danh sách tọa độ không bao gồm vị trí chỉ mục đầu tiên và cuối cùng. Cuối cùng, tôi nhận thấy ý tưởng sử dụng phạm vi tùy chỉnh của họ hiệu quả hơn nhiều

Đường dẫn tối ưu hóa cuối cùng đến giải pháp sử dụng siêu tham số do mã sự cố cung cấp

Quỹ đạo kết quả phù hợp hơn với cách người điều khiển phương tiện sẽ vận hành, tức là rẽ trước một góc cua