7.155 동적 환경에서의 적응적 재계획

1. 동적 환경의 특성

실세계 로봇 운용 환경에서는 장애물의 이동, 새로운 장애물의 출현, 기존 장애물의 소멸 등 환경이 시간에 따라 변화한다. 보행자, 차량, 협동 로봇, 이동하는 물체 등이 동적 장애물에 해당한다. 정적 환경에서 사전 계획된 경로는 동적 환경에서 유효하지 않으므로, 실시간으로 환경 변화를 감지하고 경로를 적응적으로 재계획(replanning)해야 한다.

2. 재계획 전략

2.1 완전 재계획

환경 변화가 감지되면 현재 위치에서 목표까지의 경로를 처음부터 다시 계획한다. 가장 단순하지만 계산 비용이 높으며, 이전 계획의 정보를 활용하지 않는다.

2.2 부분 재계획

변화에 의해 무효화된 경로 구간만을 국소적으로 재계획한다. 유효한 경로 구간은 보존하고, 무효화된 부분만 수정하여 전체 재계획에 비해 계산 비용을 현저히 줄인다.

2.3 증분적 탐색

D* Lite와 같은 증분적 그래프 탐색 알고리즘은 환경 변화에 의해 영향받는 노드만을 선택적으로 재확장(re-expand)하여 최적 경로를 갱신한다. 변화가 소규모이면 소수의 노드만 재처리하면 되므로 매우 효율적이다.

3. 이동 지평 재계획

3.1 MPC 기반 재계획

모델 예측 제어의 이동 지평 구조가 자연스러운 재계획 프레임워크를 제공한다. 매 제어 주기에서 최신 센서 정보를 반영하여 유한 지평의 최적화 문제를 다시 풀므로, 환경 변화에 대한 지속적 적응이 내재되어 있다.

$\mathbf{u}_k^* = \arg\min_{\mathbf{u}} J(\mathbf{x}_k, \mathbf{u}; \mathcal{E}_k)$

여기서 $\mathcal{E}_k$ 는 시각 $k$ 에서의 환경 모델(동적 장애물의 현재 위치 및 예측 궤적)이다.

3.2 웜 스타트에 의한 가속

이전 해를 초기점으로 활용하면 재계획에 필요한 최적화 반복이 현저히 감소한다. 연속적인 재계획에서 환경 변화가 점진적이면, 이전 해와 새 해의 차이가 작으므로 소수의 반복으로 수렴한다.

4. 동적 장애물의 예측

재계획의 품질은 동적 장애물의 미래 운동 예측의 정확도에 크게 의존한다.

4.1 등속 예측(Constant Velocity Prediction)

장애물의 현재 속도가 유지된다고 가정하여 미래 위치를 외삽한다.

$\mathbf{o}(t + \tau) = \mathbf{o}(t) + \tau\dot{\mathbf{o}}(t)$

단순하지만 방향 전환이나 가감속을 예측하지 못한다.

4.2 의도 기반 예측

보행자나 차량의 행동 패턴을 모델링하여 다수의 가능한 미래 궤적을 확률적으로 예측한다. 가우시안 과정, 순환 신경망(RNN), 사회력 모델(Social Force Model) 등이 사용된다.

4.3 불확실성의 반영

예측의 불확실성을 타원체(공분산 타원)로 표현하고, 불확실성이 확대됨에 따라 안전 마진을 증가시키는 보수적 접근이 채택된다. 예측 지평이 길수록 불확실성이 커지므로, 먼 미래의 계획은 보수적으로, 가까운 미래의 계획은 적극적으로 설정한다.

5. 반응 시간과 계산 예산

동적 환경에서의 재계획은 반응 시간(reaction time)에 의해 제한된다. 환경 변화의 감지부터 재계획된 경로의 실행까지의 지연이 커지면, 그 사이 환경이 추가로 변화하여 재계획의 유효성이 저하된다.

재계획 주기 $T_{replan}$ 의 선택은 환경의 동적 특성과 계산 자원에 의존한다.

느린 환경(공장 내 이동 장애물): $T_{replan} = 0.5 \sim 2$ s
빠른 환경(도로 교통): $T_{replan} = 50 \sim 200$ ms
매우 빠른 환경(드론 경주): $T_{replan} = 10 \sim 50$ ms

6. 안전 보장

동적 환경에서 재계획 중 안전을 보장하기 위한 방법은 다음과 같다.

비상 정지 궤적: 모든 시점에서 안전하게 정지할 수 있는 비상 궤적을 유지한다. 재계획이 시간 내에 완료되지 않으면 비상 궤적을 실행한다.

안전 집합(Safe Set): 도달 가능 집합(reachable set) 분석에 기반하여, 로봇이 안전 정지 상태에 도달할 수 있는 상태의 집합을 사전에 계산한다. 재계획된 궤적이 안전 집합을 벗어나지 않도록 제약한다.

이중 계층 구조: 안전 계층(safety layer)이 계획 계층의 출력을 감시하고, 안전 위반이 감지되면 즉시 안전 행동으로 전환한다.

7. 참고 문헌

Koenig, S., & Likhachev, M. (2002). “D* Lite.” Proceedings of the AAAI Conference on Artificial Intelligence, 476–483.
Borrelli, F., Bemporad, A., & Morari, M. (2017). Predictive Control for Linear and Hybrid Systems. Cambridge University Press.
Fridovich-Keil, D., Herbert, S. L., Bansal, S., & Tomlin, C. J. (2020). “Confidence-Aware Motion Prediction for Real-Time Collision Avoidance.” IJRR, 39(2-3), 250–265.
Fox, D., Burgard, W., & Thrun, S. (1997). “The Dynamic Window Approach to Collision Avoidance.” IEEE Robotics and Automation Magazine, 4(1), 23–33.

version: 1.0