Anytime Motion Planning

다른 이름: anytime planning, anytime planner
카테고리: Planning & manipulation › Motion planning
태그: motion-planning, sampling-based-planning, optimal-planning, real-time, bounded-computation

유효한 경로를 빠르게 돌려준 다음 시간이 허락하는 동안 계속 개선하여, 플래너를 언제 멈추든 쓸 수 있는 답이 있도록 하는 모션 플래닝.

정의

애니타임 모션 플래너(anytime motion planner)는 실행 가능하고 충돌 없는 첫 해를 가능한 한 일찍 내놓은 다음, 남은 시간을 그 해를 개선하는 데 쓰며, 보통 경로 길이, 실행 시간 또는 다른 비용을 낮춘다. 첫 해를 얻은 뒤에는 어느 순간이든 지금까지 가장 좋은 답을 가지고 있어서, 중단되면 그 답을 돌려줄 수 있다. 이 아이디어는 인공지능에서 더 넓게 쓰이는 애니타임 알고리즘 개념에서 왔으며, 1980년대 후반 Dean과 Boddy가 도입했다. 여기서는 해의 품질과 계산 시간을 맞바꾸며, 둘 사이의 관계를 성능 프로파일(performance profile)로 기술한다.

그래프 탐색에서 애니타임 동작은 보통 가중치를 주어 부풀린 휴리스틱으로 먼저 탐색한 뒤, 앞선 탐색 결과를 재사용하면서 가중치를 줄여 가는 방식으로 얻으며, Anytime Repairing A(ARA)가 그 예이다. 샘플링 기반 계획에서는 RRT나 확률적 로드맵의 PRM 변형 같은 점근적 최적 플래너가 본래 애니타임이다. 이들은 첫 해를 찾은 뒤에도 계속 샘플링하고 연결을 다시 잇으며, 샘플 수가 늘어남에 따라 가장 좋은 경로의 비용이 최적값으로 다가간다. Informed RRT와 Batch Informed Trees(BIT)는 더 나은 경로가 아직 있을 수 있는 영역으로 샘플을 제한해 개선 단계를 빠르게 한다. 평범한 급속 탐색 랜덤 트리**는 목표에 연결되는 순간 멈추므로 이런 의미의 애니타임이 아니지만, 재시작이나 후처리를 덧씌울 수는 있다.

시간에 따른 개선이 매끄러운 경우는 드물다. 비용은 흔히 계단식으로 떨어지는데, 특히 플래너가 장애물 사이의 다른 틈을 지나는 경로, 즉 새로운 호모토피 클래스에 속한 경로를 찾을 때 그렇다. 또 오랫동안 거의 아무 이득이 없는 구간이 이어지기도 한다. 그래서 언제 멈출지 정하는 것 자체가 하나의 문제가 된다. 너무 일찍 멈추면 품질을 잃고, 너무 늦게 멈추면 로봇이 움직이는 데 쓸 수 있었던 시간을 잃는다. 고정된 시간 예산이 흔한 관행이고, 메타 추론(meta-reasoning) 방법은 추가 계산이 더 이상 가치가 없는 시점을 학습하거나 추정한다.

중요한 이유

로봇이 계획에 쓸 수 있는 시간이 고정되어 있고 미리 알려진 경우는 드물다. 애니타임 플래너는 거의 즉시 안전한 대비책을 주고 남는 시간을 더 나은 움직임으로 바꾸므로, 마감 시간 안에 행동해야 하면서도 경로 품질, 에너지, 사이클 타임을 중요하게 여기는 시스템에 알맞다.

주요 응용

조작 파이프라인에서 질의별 시간 예산 안에서 하는 팔의 모션 플래닝
고정된 제어 주기에 맞춰 행동해야 하는 이동 로봇과 차량의 재계획
경로가 짧을수록 배터리가 절약되는 비행 로봇의 경로 계획
ARA* 방식의 가중치 감소를 쓰는 격자와 래티스 위의 휴리스틱 그래프 탐색
계획을 멈추고 행동을 시작할 시점을 정하는 메타 추론 연구

실제 사례

한 모바일 매니퓰레이터가 OMPL 같은 라이브러리의 점근적 최적 샘플링 기반 플래너로 팔의 움직임을 계획한다. 질의마다 시간 예산이 주어지며, 플래너는 보통 그 예산의 앞부분에서 첫 경로를 찾고 이후 계속 경로를 줄여 나간다. 팀은 기록해 둔 많은 질의에 대해 경과 시간에 따른 최선 비용을 기록하고, 이득의 대부분이 초반에 생기며 장애물을 도는 더 짧은 길을 늦게 찾을 때 가끔 크게 떨어진다는 것을 확인한다. 팀은 예산을 늘 다 쓰는 대신, 정해진 구간 동안 비용이 개선되지 않으면 멈추거나 학습된 정지 규칙을 쓰고, 그다음 결과에 지름길 처리(shortcutting)와 시간 매개변수화를 적용한 뒤 제어기로 보낸다.

흔한 오해

애니타임이라면 첫 해가 최적에 가깝다 — 첫 해는 흔히 최적과 거리가 멀며, 품질은 플래너를 얼마나 오래 실행하느냐에 달려 있다
비용은 시간에 따라 꾸준히 개선된다 — 보통 고르지 않은 계단식으로 떨어지고, 계단 사이에 긴 정체 구간이 있다
점근적 최적성은 시간 예산 안에서 좋은 경로를 보장한다 — 점근적 최적성은 계산이 한없이 늘어날 때의 극한만 기술할 뿐, 유한한 마감 시간에 대해서는 아무것도 말하지 않는다
시간 예산을 모두 쓰는 것이 언제나 최선이다 — 계획에 쓴 시간은 움직이지 못한 시간이므로, 일찍 멈추는 편이 더 나은 절충인 경우가 많다

알아야 할 사람

샘플링 기반 또는 탐색 기반 플래너를 설정하는 모션 플래닝 엔지니어
실시간 제약 아래에서 일하는 모바일 매니퓰레이션 및 내비게이션 개발자
제한된 계산 아래의 계획을 연구하는 로봇공학 연구자
최적 모션 플래닝을 배우는 학생

Open Source Robotics

Anytime Motion Planning

정의

중요한 이유

주요 응용

실제 사례

흔한 오해

알아야 할 사람

관련 기술

관련 용어

관련 프로젝트