오늘 끝나면
경로 계획
- ✓경로 계획의 핵심 문제를 한 문장으로 설명한다
- ✓오른쪽 실습에서 경로이 어떻게 움직이는지 관찰한다
- ✓다음 강의와 이어지는 한계를 말할 수 있다
실습 미션
장애물을 피해 어디로 어떻게 갈까 이 문장이 실제로 무슨 뜻인지 실습에서 한 번 손으로 확인한다.
성공 조건
- □실습의 기본값을 먼저 관찰
- □입력값이나 모드를 한 번 이상 바꿔 결과 비교
- □왜 결과가 바뀌었는지 한 문장으로 설명
Physical AI · 17
경로
계획
지도는 있다. 내가 어디 있는지도 안다(SLAM). 이제 질문은 하나다.
출발에서 목표까지, 장애물을 피해 어느 길로 갈 것인가.
그 길을 미리 찾아내는 일이 경로 계획(path planning)이다.
출발에서 목표로, 장애물은 피해서
경로 계획이 푸는 문제는 한 줄로 정리된다. 출발 위치에서 목표 위치까지, 장애물에 부딪히지 않는 길을 찾는 것이다.
로봇이 움직일 수 있는 빈 곳을 자유공간(free space)이라 하고, 못 가는 데를 장애물이라 한다.
좋은 경로는 자유공간 안에만 머물러야 한다. 벽을 뚫고 가는 길은 답이 아니다.
여기엔 두 층이 있다.
어디를 지나갈지 큰 줄기를 잡는 일이 전역 계획(global planning)이다. 지도 전체를 보고 길을 그린다.
코앞의 사람이나 튀어나온 의자를 그때그때 피하는 일이 지역 계획(local planning)이다. 센서로 즉석에서 길을 살짝 틀어준다.
이번 강은 지도를 보고 큰 줄기를 그리는 전역 계획에 집중한다.
핵심은 가능한 길이 무수히 많은데 그중 하나를 어떻게 빠르게 찾느냐다.
벽을 뚫지 않고 S에서 G를 잇는 길 하나, 그게 답이다. 그런 길은 보통 여러 개고, 그중 좋은 것을 고른다.
연속 공간을 그래프로 바꾸기
실제 공간은 연속이다. 점이 무한히 많아서 그대로는 뒤질 수 없다.
그래서 먼저 공간을 셀 수 있는 조각으로 추상화한다.
가장 단순한 방법이 격자(grid)다. 바닥을 칸칸이 쪼갠다.
빈 칸은 노드(node)가 되고, 옆 칸으로 가는 길은 간선(edge)이 되며, 이동 비용은 보통 1이다.
벽이 깔린 칸은 통째로 막힌 노드로 처리한다.
이렇게 하면 길찾기 문제가 그래프 탐색 문제로 바뀐다.
출발 노드에서 목표 노드까지 막힌 칸을 빼고 최소 비용으로 잇는 경로를 찾는, 익숙한 모양이 된다.
격자 말고도 길목마다 점을 뿌려 잇는 로드맵이나 무작위로 점을 뿌리는 방식도 있다.
공통점은 하나다. 연속 공간을 노드와 간선으로 바꿔야 알고리즘이 비로소 돌아간다는 것이다.
빈 칸은 노드, 옆 칸으로 가는 길은 간선(비용 1), 벽은 막힌 노드다. 길찾기가 그래프 탐색이 된다.
A*, 목표 쪽으로 똑똑하게
그래프가 생겼으면 탐색한다. 대표 알고리즘이 A*(에이스타)다.
A*는 각 칸을 f = g + h 점수로 평가한다.
g는 출발에서 여기까지 이미 든 비용이고, h는 여기서 목표까지 남았을 거리의 추정치(휴리스틱)로 보통 맨해튼 거리를 쓴다.
f가 가장 작은 칸부터 펼치기 때문에 탐색이 목표 방향으로 곧장 쏠린다.
벽을 세워 보면 차이가 드러난다.
A*는 사방으로 막 퍼지지 않고 목표 쪽 후보만 골라 펴서 적게 확장하고도 길을 찾는다. ‘확장한 칸’ 수치를 보면 된다.
h가 실제 거리를 넘겨 짚지만 않으면(admissible) 찾은 경로는 항상 최단임이 보장된다.
휴리스틱을 0으로 두면 사방으로 고르게 퍼지는 다익스트라가 되고, g를 무시하면 목표만 보고 달리는 탐욕 탐색이 된다.
A*는 그 둘 사이에서 비용과 방향감을 함께 보는 균형점이다.
격자가 버거우면 RRT
A*는 격자에선 강력하다. 그런데 로봇 팔처럼 관절이 6~7개면 격자 칸 수가 폭발한다. 차원의 저주다.
이럴 땐 공간을 다 쪼개지 않고 무작위로 점만 찍어 탐색한다. 대표가 RRT(Rapidly-exploring Random Tree)다.
출발점에서 트리를 키운다. 빈 곳에 점 하나를 무작위로 찍고, 트리에서 가장 가까운 가지를 그쪽으로 조금 뻗는다. 충돌이 나지 않으면 가지를 추가한다.
이걸 수천 번 반복하면 트리가 공간을 빠르게 더듬어 결국 목표에 닿는다.
격자를 통째로 만들 필요가 없어 고차원에서도 돌아간다. 자율주행 차의 주차 경로나 로봇 팔 모션 플래닝에서 표준으로 쓴다.
대신 무작위라 경로가 들쭉날쭉 꺾인다. 그래서 보통 RRT*로 점점 다듬고, 찾은 길을 한 번 더 매끄럽게 펴는(smoothing) 후처리를 붙인다.
A*는 길을 격자로 빈틈없이 찾고, RRT는 무작위로 듬성듬성 찾는다. 문제의 차원에 맞춰 고르면 된다.
빈 곳에 점을 찍고 가장 가까운 가지를 그쪽으로 뻗는다. 수천 번 반복하면 목표에 닿는다. 고차원에 강하다.
최단만이 답이 아니다 · 움직이면 다시 짠다
가장 짧은 길이 항상 좋은 길은 아니다. 벽에 바싹 붙은 최단 경로는 조금만 흔들려도 들이받는다.
그래서 실제 계획은 세 가지를 저울질한다.
최단은 거리와 시간을 줄이고, 안전은 장애물과 여유 간격(clearance)을 두며, 부드러움은 급한 꺾임을 줄여 로봇이 따라갈 수 있게 한다.
벽에서 살짝 떨어지고 코너를 둥글린 길이 1칸 짧은 직선보다 나은 경우가 많다.
더 큰 문제는 세상이 가만있지 않는다는 것이다.
사람이 끼어들고 문이 닫히면 미리 짠 길이 막힌다. 멈춰서 처음부터 다시 풀면 너무 느리다.
그래서 끊임없이 재계획(replanning)한다. 새 장애물이 뜨면 영향받은 부분만 빠르게 고쳐 다시 그린다. D*와 D* Lite가 이 증분 재탐색의 대표다.
계획은 한 번 짜고 끝이 아니라 센서가 주는 새 정보로 계속 갱신되는 살아있는 과정이다.
Q. 경로 계획이 푸는 문제는?
출발에서 목표까지, 장애물을 피해 갈 수 있는 길을 찾는 것이다.연속 공간을 격자나 그래프로 바꾼 뒤 A*나 RRT 같은 탐색으로 자유공간 안의 경로를 찾는다.
최단만 보지 않고 안전(여유 간격)과 부드러움까지 저울질하며, 움직이는 장애물이 생기면 재계획으로 길을 고쳐 그린다.
새 장애물이 뜨면 영향받은 부분만 빠르게 고쳐 그린다. D* Lite의 증분 재탐색이다.