Motion Planning và Obstacle Avoidance
Từ configuration space đến đường đi, local replanning và các giới hạn của collision checking.
Motion planning tìm chuyển động đáp ứng ràng buộc robot và môi trường. Một đường trên bản đồ 2D chưa phải trajectory khả thi theo thời gian, và một lần collision check không bảo đảm môi trường sẽ đứng yên.
Mục tiêu học tập
- Phân biệt path, trajectory, planner và controller.
- Giải thích configuration space và obstacle inflation.
- Chạy một ví dụ tìm đường lưới và nêu phạm vi đúng của nó.
Robot có kích thước và ràng buộc
Một chấm có thể chui qua khe hẹp mà robot thật không qua được. Khi tìm đường, phải tính cả thân robot; với cánh tay, khuỷu có thể đụng vật cản dù đầu kẹp đi đúng đường.
Path là tuyến hình học; trajectory thêm thời gian và thường cả tốc độ. Controller mới biến mục tiêu chuyển động thành lệnh thực tế.
Configuration space biểu diễn trạng thái cấu hình như vị trí/hướng mobile robot hoặc góc khớp. Trong ví dụ robot tròn trên mặt phẳng, có thể phóng to chướng ngại theo bán kính robot rồi tìm đường cho tâm. Đây là đơn giản hóa có giả định.
Robot có giới hạn quay, gia tốc hoặc nonholonomic constraints cần planner và trajectory generation phù hợp. Nội suy giữa hai cấu hình cũng phải được kiểm tra va chạm, không chỉ hai đầu mút.
Collision-free trong không gian cấu hình khác với free cell của một bản đồ thiếu quan sát. Độ phân giải discretization ảnh hưởng việc bỏ sót vật cản nhỏ. Margin nên phản ánh sai số map và localization, nhưng margin lớn có thể loại đường khả thi.
Động lực học có thể đưa bài toán sang state space gồm vận tốc. Những bảo đảm completeness hoặc optimality của planner chỉ đúng dưới giả định về không gian, kiểm tra hợp lệ và tài nguyên tính toán đã nêu.
Tìm kiếm đường ứng viên
Trên lưới, đi lần lượt các ô kề giúp tìm đường vòng chướng ngại. Nếu mỗi bước có cùng chi phí, duyệt theo từng lớp khoảng cách sẽ tìm đường ít bước nhất khi đích có thể tới được.
BFS phù hợp lưới hữu hạn với cạnh cùng trọng số. Dijkstra hỗ trợ cost không âm; A* thêm heuristic và có điều kiện cho tính tối ưu. Trong không gian liên tục nhiều chiều, OMPL cung cấp nhiều sampling-based planners với giả định và trade-off riêng.
A* graph search cần xử lý việc mở lại node khi heuristic không consistent, hoặc dùng điều kiện thuật toán phù hợp. Các tính chất của A* trên graph không tự chuyển thành bảo đảm cho robot động ngoài đời.
RRT và RRT* khác về mục tiêu và tính chất tiệm cận; finite-time path quality vẫn cần đo. Tách thời gian collision checking khỏi các bước mở rộng khi phân tích hiệu năng planner.
Vật cản động và đường đã cũ
Người đi ngang có thể chặn đường vừa tìm. Robot cần quan sát mới và một cách giảm tốc, dừng hoặc đổi đường. Không nên cứ bám tuyến cũ vì planner đã từng báo thành công.
Global planning xác định tuyến tổng thể; local planning/control xử lý trạng thái và chướng ngại gần hiện tại. Đặt freshness limit và timeout. Mã BFS chỉ dùng bản đồ cố định, robot là điểm và chuyển động bốn hướng.
Chọn horizon và stopping distance theo động học cùng latency. Khi không có nghiệm trong budget, trạng thái fallback phải được thiết kế trước. Mô phỏng thành công không tự xác nhận an toàn phần cứng; cần kiểm thử trong điều kiện vận hành cụ thể.
Workflow & kiến trúc
Ứng dụng & giới hạn
- Lập tuyến trên bản đồ tĩnh trong mô phỏng.
- Phân tích collision model và replanning cho robot.
Điểm mạnh
Tách mô hình môi trường, ràng buộc và tìm kiếm để kiểm tra từng phần.
Giới hạn cần nhớ
Bản đồ, kích thước robot và latency sai có thể làm một đường tính được không khả thi ngoài đời.
Thử trong một project nhỏ
Thêm bán kính robot tương đương một ô bằng obstacle inflation. So đường còn tồn tại hay không; giải thích vì sao thuật toán đúng trên lưới vẫn chưa là giải pháp điều khiển.
from collections import deque
blocked = {(1, 1), (1, 2)}
start, goal = (0, 0), (3, 3)
queue, parent = deque([start]), {start: None}
while queue:
current = queue.popleft()
if current == goal:
break
x, y = current
for nxt in [(x+1,y), (x-1,y), (x,y+1), (x,y-1)]:
a, b = nxt
if 0 <= a < 4 and 0 <= b < 4 and nxt not in blocked and nxt not in parent:
parent[nxt] = current
queue.append(nxt)
path = []
node = goal if goal in parent else None
while node is not None:
path.append(node)
node = parent[node]
path.reverse()
assert path[0] == start and path[-1] == goal
assert all(cell not in blocked for cell in path)
print(path)BFS trên lưới giả định 4×4, robot là điểm, cost cạnh bằng nhau; không chạy robot và không xử lý vật cản động.