Đề tài Áp dụng giải thuật MOPSO tìm đường đi cho robot

Áp dụng giải thuật MOPSO t ìm đường đi cho robot GVHD: PGS.TS Huỳnh Thị Thanh Bình HS: Dương Công Hậu MSSV: 20183526 2021.0 8 .1 3 Tính toán tiến hóa **Robot path planning in uncertain environment using multi-objective particle swarm optimization Yong Zhang n , Dun-wei Gong n , Jian-hua Zhang ( 2018) 1 Nội dung 01. 0 3 . Giới thiệu đề tài Môi trường 0 4 . 0 5 . Giải thuật Đánh giá 0 6 . Kết luận 0 7 . Tài liệu tham khảo 2 0 2 . Phát biểu bài toán 1. Giới thiệu đề tài Giải thuật PSO Được phát triển bởi Dr.Eberhart và Dr.Kennedy 1995 Dựa vào hành vi của bầy chim hay đàn cá trong quá trình tìm kiếm thức ăn Các công thức cập nhật vị trí X[i] và V[i] V[i] = w*V[i] + Cp*rand(0,1)*(pBest[i] - X[i]) + Cg*rand(0,1)*(gBest - X[i]) (1) X[i] = X[i] + V[i] (2) Trong đó: rand(0,1) là số ngẫu nhiên trong khoảng (0,1) Cp, Cg là các hệ số học w biểu thị trọng lượng quán tính 3 Bài toán tìm đường đi cho robot Ngày nay robot được áp dụng trong nhiều lĩnh vực như quân sự, tìm đường đi,... 4 5 2. Phát biểu bài toán Bài toán tìm đường đi cho robot trong môi trường chưa biết trước Input: điểm xuất phát, điểm kết thúc, các vật thể và vòng nguy hiểm Output: đường đi tối ưu thỏa mãn hàm mục tiêu và ràng buộc Hàm mục tiêu: Độ dài đường đi: tối thiểu độ dài quãng đường Độ trơn tru : tối đa khoảng cách đến vòng nguy hiểm Ràng buộc : Mức độ va chạm của đường đi với các vật thể phải bằng không 3. Môi trường Biểu diễn môi trường Môi trường được biểu diễn dưới dạng 2D và hệ trục tọa độ Oxy Môi trường gồm các vật thể và vòng nguy hiểm, điểm bắt đầu và điểm đích đến Mô hình hóa môi trường xoay trục tọa độ phân đoạn đường thẳng nối giữa điểm xuất phát và đích đến thành n đoạn thẳng 6 7 Phân đoạn đường thẳng nối giữa điểm bắt đầu và điểm kết thúc Cố định hoành độ, tìm tung độ 3. Môi trường Hàm mục tiêu và ràng buộc Hàm mục tiêu Độ dài đường đi 8 9 Hàm mục tiêu và ràng buộc Độ trơn tru Khoảng cách nhỏ nhất và lớn nhất từ vòng nguy hiểm đến đường đi Ràng buộc Trung bình số lần va chạm của đường đi với vật thể Bài toán: Ràng buộc 10 Tối thiểu hàm mục tiêu cv # 0 Hàm mục tiêu và ràng buộc 4. Giải thuật MOPSO Quan hệ trội ràng buộc 11 Mã hóa cá thể Hàm tối ưu đa mục tiêu => Quan hệ trội Quan hệ trội ràng buộc: xi tốt hơn xj khi 12 4. Giải thuật MOPSO Cập nhật pbest Cập nhật kho dữ liệu kho khả quan kho không khả quan Cập nhật dữ liệu: khi kho chưa đầy thì thêm dữ liệu vào kho đã đầy : nếu dữ liệu trội hơn giá trị nào trong kho thì loại bỏ giá trị bị trội và thêm vào dữ liệu mới, nếu không thì loại bỏ dữ liệu mới 4. Giải thuật MOPSO 13 Cập nhật gbest Cập nhật vị trí từng cá thể 14 4. Giải thuật MOPSO 4. Giải thuật MOPSO 15 Triển khai 5 . Đánh giá 16 5. Đánh giá 17 18 6. Kết luận Hiểu được cách áp dụng thuật toán MOPSO trong bài toán tìm đường cho robot trong môi trường chưa biết trước Chưa áp dụng được các phương pháp khác 19 7. Tài liệu tham khảo Robot path planning in uncertain environment using multi-objective particle swarm optimization Yong Zhang n , Dun-wei Gong n , Jian-hua Zhang, (2018) 20 21