💻 computer science

When Automata Meet Streams: Temporal Logic Compilation for Stream-Based Robotics Task and Motion Planning

이 논문은 SAM-TD를 소개하는데, 이는 회귀된 오토마타 가드(automaton guards)를 액션 스키마에 임베딩함으로써 유한 트레이스에 대한 임의의 선형 시제 논리(Linear Temporal Logic) 제약 조건을 강제하고, 하위 플래너를 수정하지 않고도 동적으로 생성된 객체들을 처리할 수 있게 하는 스트림 기반 작업 및 동작 계획(Task and Motion Planning)을 가능하게 하는 컴파일 방식이다.

원저자: Sayem Nazmuz Zaman, Cyrus Neary

게시일 2026-08-21

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Sayem Nazmuz Zaman, Cyrus Neary

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

로봇은 단순히 A 지점에서 B 지점으로 이동하는 것 이상의 역할을 수행하도록 점점 더 많은 기대를 받고 있습니다. 로봇은 주방, 실험실, 공장과 같이 무질서한 실제 환경에서 복잡하고 다단계적인 작업을 수행할 것을 요구받고 있습니다. 성공하기 위해서 로봇은 두 가지 뚜렷한 문제를 동시에 해결해야 합니다. 첫째, 로봇은 "컵을 집는다" 또는 "문을 연다"와 같은 논리적 단계의 순서인 상위 수준의 계획이 필요합니다. 둘째, 로봇은 컵을 잡는 정확한 각도나 탁자 다리를 피하는 매끄러운 경로와 같이, 실제로 그 일들을 어떻게 수행할지에 대한 연속적이고 물리적인 세부 사항을 파악해야 합니다. 이 이중 과제는 작업 및 동작 계획(task and motion planning)이라고 알려져 있습니다. 컴퓨터는 논리적 단계에는 능숙하지만, 물리적 세부 사항은 로봇이 해결책을 찾는 과정에서 실시간으로 생성되므로, 계획이 전개됨에 따라 변화하는 움직이는 목표를 만들어냅니다.

시간과 안전에 관한 규칙을 추가하면 난이도는 더욱 깊어집니다. 화학 실험실의 로봇은 환기 시스템이 켜지기 전까지 위험한 화학 물질을 섞을 수 없습니다. 드론은 항상 충전 스테이션으로 돌아올 수 있는 경로를 확보하고 있어야 합니다. 이것들은 시간적 제약(temporal constraints)입니다. 즉, 사건의 순서를 규정하거나 작업 내내 특정 조건이 유지되어야 함을 요구하는 규칙들입니다. 수십 년 동안 연구자들은 로봇이 이러한 규칙을 따르도록 강제하는 방법들을 개발해 왔지만, 그 방법들은 로봇이 고정되고 알려진 일련의 물체들을 가지고 작업한다고 가정했습니다. 로봇이 계획 과정에서 새로운 물리적 가능성을 만들기 위해 실시간 생성기(on-the-fly generators)를 사용하는 경우, 기존의 방법들은 무너집니다. 그 방법들은 로봇이 상호작용할 수 있는 대상의 목록이 끊임없이 늘어나고 변화하는 상황을 처리할 수 없기 때문입니다.

브리티시 컬럼비아 대학교의 한 연구팀은 이 특정 문제를 해결하기 위한 새로운 방법을 개발했습니다. 그들은 토큰 파괴를 동반한 동기식 행동 모니터링(Synchronous Action Monitoring with Token Destruction, SAM-TD)이라는 시스템을 만들었는데, 이는 로봇이 계획하는 동안 새로운 물리적 옵션들을 발명하면서도 복잡한 시간 기반 규칙들을 따를 수 있게 해줍니다. 핵심 아이디어는 규칙들을 배경에서 실행되는 일련의 상태 머신(state machines), 즉 간단한 추적 시스템으로 변환하는 것입니다. 로봇이 잠재적인 행동을 고려할 때, 시스템은 해당 행동이 규칙을 위반하는지 확인합니다. 만약 어떤 행동이 안전 규칙을 위반하거나 순서 제약을 유발할 경우, 시스템은 반드시 그 행동을 즉시 차단하는 것은 아닙니다. 대신, 로봇이 최종 목표에 도달하기 위해 필요한 특별한 "유효성 토큰(validity token)"을 제거합니다.

이 메커니즘은 로봇의 계획 소프트웨어가 핵심적인 역할을 수행할 수 있게 한다는 점에서 영리합니다. 로봇의 탐색 알고리즘은 목표를 향한 가장 효율적인 경로를 찾도록 설계되어 있습니다. 유효성 토큰이 제거되면, 알고리즘은 현재의 경로가 더 이상 성공적인 결과로 이어질 수 없음을 깨닫게 되는데, 이는 목표 달성을 위해 해당 토큰이 반드시 존재해야 하기 때문입니다. 그러면 알고리즘은 자연스럽게 해당 경로를 버리고 다른 경로를 찾으며, 금지된 동작에 대한 물리적 세부 사항을 계산하는 데 시간을 낭비하기 전에 효과적으로 나쁜 옵션들을 제거합니다. 이 접근 방식은 로봇이 마주칠 수 있는 모든 물체를 사전에 목록화할 필요 없이 작동하며, 이는 계획 과정 중에 새로운 물체나 위치가 발견되는 작업에서 매우 중요합니다.

연구진은 세 가지 로봇 환경인 주방 설정, 탁자 위 조작 작업, 그리고 분류 구역에서 이 시스템을 테스트했습니다. 이 시뮬레이션들에서 그들은 빨간 블록을 움직이기 전에 흰색 블록을 놓아야 하거나, 위험 구역에 들어가는 것을 금지하는 것과 같은 다양한 규칙들을 도입했습니다. 모든 경우에서, 시스템은 모든 규칙을 만족하는 계획으로 로봇을 성공적으로 안내했습니다. 실험 결과, 이러한 규칙을 설정하는 데 걸리는 시간은 추가된 규칙의 수에 따라 선형적으로 증가했으며, 이는 제약 조건이 더 복잡해지더라도 시스템이 효율성을 유지함을 의미합니다. 결정적으로, 이 방법은 로봇이 결국 실패할 경로를 탐색하며 시간을 낭비하는 것을 방지하여 상당한 계산 노력을 절감했습니다.

또한 이 연구는 표준적인 비-스트리밍(non-streaming) 계획 문제에 사용되는 기존 기술들과 이 새로운 방법을 비교했습니다. 결과는 이 새로운 시스템이 이러한 더 단순한 작업들을 위한 최신 방법들만큼이나 빠르고 효과적임을 보여주었으며, 이는 복잡하고 역동적인 환경을 다루는 능력이 표준적인 문제에서의 성능 저하를 초래하지 않는다는 것을 입증했습니다. 연구진은 과정 중 가장 비용이 많이 드는 부분은 규칙을 체크하는 것 자체가 아니라, 로봇의 지침을 컴퓨터가 실행할 수 있는 형식으로 변환하는 표준적인 작업이라는 것을 발견했습니다. 이는 새로운 방법이 새로운 병목 현상을 일으키지 않고 기존의 계획 도구들과 매끄럽게 통합된다는 것을 확인시켜 줍니다.

동적인 물체 생성과 시간 기반 규칙 사이의 불일치를 해결함으로써, 이 연구는 로봇이 구조화되지 않은 환경에서 더 정교하고 안전이 중요한 작업을 수행할 수 있는 길을 열어줍니다. 이는 로봇이 작업의 구체적인 물리적 세부 사항이 작업을 시작할 때까지 완전히 알려지지 않은 경우에도, 작업의 순서와 안전 한계에 대한 엄격한 지침을 받을 수 있음을 보여줍니다. 이러한 발견은 미래의 로봇이 환경이 어떻게 변하든 상관없이, 단지 일을 완수하는 것뿐만 아니라 올바르고 안전하며 논리적인 순서로 일을 수행할 것이라는 확신을 가지고 가정과 실험실에 배치될 수 있음을 시사합니다.

기술 요약: 스트림 기반 TAMP를 위한 SAM-TD

문제 정의

스트림 기반 작업 및 모션 계획(Stream-based Task and Motion Planning, TAMP)은 이산적 심볼릭 계획과 연속적 기하학적 추론을 통합한다. PDDLStream과 같은 시스템은 "스트림(streams)"—검색 과정 중에 온디맨드 방식으로 기하학적 객체(포즈, 그라스프, 궤적)를 동적으로 생성하는 블랙박스 생성기—을 활용한다. 이는 고전적 계획법이 고정되고 유한한 객체 집합을 가정하는 것과 대조적으로, 잠재적으로 무한한 객체 집합을 생성한다.

유한 트레이스(finite traces)에 대한 선형 시제 논리(LTLf)는 로보틱스의 안전 필수 순서, 불변성 및 활성 제약을 인코딩하기 위한 표준 형식론이지만, 기존의 컴파일 기술은 스트림 기반 TAMP와 호환되지 않는다. 고전적인 방법들은 (검색 전 모든 객체를 열거하는) 성급한 그라운딩(eager grounding)을 사용하거나 동기화 액션을 삽입하는데, 이는 객체 집합이 미지의 상태로 남아 있고 반복적으로 성장하는 상황에서는 실패한다. 결과적으로, 스트øm 기반 솔버를 수정하거나 방대한 양의 기하학적 객체 라이브러리를 사전 샘플링하지 않고 임의의 LTLf 제약을 강제할 수 있는 기존의 방법은 존재하지 않는다.

방법론: SAM-TD

저자들은 PDDLStream 문제의 리프티드 액션 스키마(lifted action schemas) 내에 LTLf 제약 모니터를 직접 임베딩하는 컴파일 프레임워크인 **SAM-TD(Synchronous Action Monitoring with Token Destruction)**를 제안한다. SAM-TD는 플래너의 검색 알고리즘이나 스트림 인스턴스화 계층을 수정하지 않고 작동한다.

핵심 구성 요소

LTLf에서 DFA로의 변환: 각 LTLf 제약은 결정적 유한 오토마타(DFA)로 변환된다. DFA는 계획 트레이스의 참인 원자 명제(atomic propositions) 시퀀스에 따라 상태를 전이하는 모니터 역할을 한다.
리프티드 액션 회귀(Lifted Action Regression): DFA 가드는 액션 후의 상태를 평가하지만, 플래너는 실행 전에 결정을 내려야 하므로, SAM-TD는 최약 전제 조건 회귀(weakest precondition regression)를 사용한다. 이는 DFA 전이 가드(액션 후 상태를 참조함)를 액션 전 상태 및 액션 파라미터에 대한 동등한 조건으로 변환한다. 이를 통해 그라운딩 전에 리프티드 액션 스키마에 대해 제약을 확인할 수 있다.
동기적 모니터 업데이트: 컴파일된 액션 스키마는 원래 도메인 액션의 실행과 맞물려 DFA 상태(플루언트 술어 $M^k_j$ 로 표현됨)를 업데이트하는 조건부 효과(conditional effects)를 포함한다. 이는 모니터가 도메인 액션마다 정확히 한 단계씩 전진하도록 보장하며, "다음(next, $X$ )"과 같은 단계 민감형 연산자의 의미론을 보존한다.
토큰 파괴 메커니즘: 위반을 처리하기 위해 SAM-TD는 공유 유효성 토큰인 Valid를 도입한다.
- 만약 전이가 DFA "싱크(sink)" 상태(수용 가능한 상태로 도달할 수 없는 비수용 상태)로 이어지면, 조건부 효과에 의해 Valid 토큰이 영구적으로 삭제된다.
- 계획 목표(planning goal)는 Valid가 참(true)일 것을 요구하도록 확장된다.
- 어떤 액션도 Valid를 다시 추가할 수 없으므로, 싱크 전이를 트리거하는 모든 브랜치는 데드 엔드(dead end)가 된다. 표준 삭제 완화 휴리스틱(예: $h_{FF}$ )은 Valid가 없는 상태에 무한한 비용을 할당하여, 값비싼 기하학적 샘플링이 일어나기 전에 심볼릭 수준에서 제약을 위반하는 브랜치를 제거한다.

설계 제약 사항

SAM-TD는 스트림 기반 TAMP의 세 가지 요구 사항을 충족하도록 명시적으로 설계되었다:

스키마 수준 인코딩: 동적인 객체 도입을 수용하기 위해 그라운디드 연산자가 아닌 리프티드 스키마에서 작동한다.
스켈레톤 보존: 동기화 액션을 삽로하지 않음으로써, 플랜-샘플-정제(plan-sample-refine) 루프에 필요한 도메인 액션과 트레이스 단계 간의 일대일 대응 관계를 유지한다.
샘플링 인식 프루닝: 제약을 위반하는 브랜치를 심볼릭 수준에서 제거하여, 유효하지 않은 플랜에 대한 기하학적 샘플링에 낭비되는 계산을 방지한다.

주요 기여

스트림 기반 TAMP를 위한 최초의 컴파일: SAM-TD는 솔버를 수정하지 않고도 임의의 LTLf 제약을 스트림 기반 TAMP 문제에 임베딩하는 최초의 기술이며, 반환된 모든 솔루션이 제약을 준수함을 보장한다.
토큰 파괴 메커니즘: 본 논문은 "토کن 파괴" 메커니즘을 DFA 싱크 전이에 대한 2상태 모니터로 식별하고 정식화하며, 이를 통해 위반 사항이 전제 조건 차단이 아닌 조건부 효과를 통해 처리될 수 있음을 입증한다.
경험적 평가: 저자들은 Kitchen, Tabletop Manipulation, ZoneSort의 세 가지 로보틱스 환경에서 LTLf 제약이 적용된 스트림 기반 TAMP에 대한 첫 번째 경험적 평가를 제공한다.
역방향 호환성: 이 방법은 표준 이산 PDDL 벤치마크에서 최첨단 시제 컴파일 기술과 경쟁력을 갖춘 것으로 나타나, 스트림 호환성이 고전적 문제의 성능을 저하시지 않음을 증명한다.

실험 결과

스트림 기반 성능: PDDLStream 환경에서 SAM-TD는 임의의 LTLf 제약을 성공적으로 강제했다. 컴파일 시간은 제약 수에 따라 선형적으로 증가했으나(제약당 약 30–80 ms), 지배적인 비용은 여전히 하위 트랜슬레이터(Fast Downward)에 의한 액션 스키마의 그라운딩 과정이었다.
절제 연구 (토큰 파괴 vs. 전제 조건 차단): SAM-PB라는 절제 변형 모델은 부정된 가드를 액션 전제 조건에 추가하여 제약을 강제했다. SAM-PB는 부정된 가드의 논리적 부정(disjunctive) 특성으로 인해 그라운드 연산자의 지수적 폭발을 겪었으며, 종종 계획 시작 전 메모리 예산을 초과했다. 반면, SAM-TD의 조건부 효과 사용은 그라운딩을 실행 가능하게 유지했다.
고전적 PDDL 벤치마크: 6개의 표준 PDDL3 태스크에서 SAM-TD는 30개 인스턴스의 100%를 해결했으며, 이는 다른 상위 방법들(BM06, TCORE, Plan4Past)의 성공률과 일치하며, 모든 인스턴스를 해결한 방법들 중 두 번째로 낮은 기하 평균 총 시간을 달성했다.

의의 및 주장

본 논문은 SAM-TD가 플래너를 변경하거나 기하학적 객체를 사전 샘플링하지 않고도 컴파일만으로 스트림 기반 TAMP에서 시제 제약을 강제할 수 있음을 보여준다고 주장한다. 엔드 투 엔드 비용은 컴파일 로직이나 검색보다는 플래너 자체의 그라운딩 과정에 의해 결정된다.

저자들은 이 연구가 시제 논리 컴파일과 스트림 기반 계획의 동적인 특성 사이의 근본적인 간극을 메운다는 점을 강조한다. 도메인 액션 스키레톤을 보존하고 토큰 파괴를 활용함으로써, SAM-TD는 기하학적 파라미터가 계획 시점까지 미지의 상태로 남아 있는 장기 실행(long-horizon) 로보틱스 작업에 복잡한 시제 명세를 적용할 수 있게 한다. 향후 연구로는 이 접근 방식을 이동형/다중 로봇 시스템 및 휴리스틱 검색과 강화 학습을 결리한 이층(bi-level) 플래너로 확장하는 것이 언급되었다.