로봇 내비게이션을 위한 최소 장애물 변위 계획의 호리즌 슬라이싱 접근법
A Horizon-slicing Approach to Minimum Obstacle Displacement Planning for Robot Navigation
한국어 초록
본 논문에서는 로봇 동작 계획(motion planning) 관점에서 최소 장애물 변위 계획(Minimum Obstacle Displacement Planning) 문제를 다룬다. 이 문제는 처음에 충돌 없는 경로가 없을 때 이동 가능한 장애물을 변위시켜 목표 지점까지의 실행 가능한 경로를 찾는 것을 포함한다. 우리는 이 문제가 계산적으로 어렵고, 특히 장애물을 평면상의 다각형으로 모델링할 때 NP-hard임을 보인다. 문헌의 다른 문제들을 일반화하는 최소 장애물 변위 문제의 정확한 공식화와 이에 대응하는 최적해 외에, 본 논문은 계산 부담이 더 적은 근사해를 제안하며, 이는 최적해와 최적 비용의 일부만큼만 차이 나며, 경로 길이와 장애물 변위량 사이의 트레이드오프를 조절할 수 있다.
원문 초록
In this paper, we investigate the Minimum Obstacle Displacement Planning problem from a robot motion planning perspective. The problem involves determining a feasible path to a goal location by displacing movable obstacles when no collision-free path initially exists. We show that this problem is computationally challenging and, in particular, NP-hard when obstacles are modeled as polygons in the plane. Besides an exact formulation of the minimum obstacle displacement problem generalizing other problems in the literature, and the associated optimal solution, this paper proposes an approximate solution that is less intensive from a computational standpoint, and differs from the optimal solution by a fraction of the optimal cost, being able to trade-off between path length and amount of obstacle displacements.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2609.22974v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
동적 환경에서의 최적 계획 수립
Optimal Planning in a Dynamic World
배경: 본 논문에서는 실행 가능한 상태나 행동의 집합이 시간에 따라 변하는 환경에서의 계획 수립(planning) 문제를 다룹니다. 예를 들어, 이동하는 장애물 사이에서의 경로 계획 문제(흔히 SIPP로 알려짐)에서는 장애물이 이동함에 따라 특정 위치에 머무를 수 있는 가능 여부가 달라질 수 있습니다. 또는 특정 기차에 탑승하는 행동은 기차가 역에 정차해 있는 동안에만 실행 가능합니다. 이러한 동적 특성으로 인해 최적 계획과 그 수행 시간은 실행이 언제 시작되는지에 따라 달라질 수 있습니다. 실제 환경에서는 계획 수립이 완료되거나 다른 에이전트(agent)의 승인이 날 때까지 실행 시작 시간을 알 수 없는 경우가 많습니다. 그러나 기존의 계획 수립 연구 대부분은 이러한 동적 특성을 무시하거나 시작 시간이 사전에 알려져 있다고 가정합니다. 이는 상태와 행동의 실행 가능성을 평가하기는 수월하게 만들지만, 일부 응용 분야에서는 비현실적입니다. 목표: 본 논문에서는 시작 시간이 알려져 있다는 가정을 완화합니다. 임의 시작 시간 계획 수립(any-start-time planning) 설정을 정의하고 이를 위한 알고리즘을 제시합니다. 방법: 시작 시간의 함수로서 최적 계획을 간결하게 인코딩하는 복합 도착 시간 함수(compound arrival time function, cATF)라는 자료구조를 제안합니다. 또한 스칼라 비용 대신 간선을 따라 함수를 전파하여 cATF를 구성하는, 휴리스틱 그래프 탐색 기반의 범용 계획 수립 알고리즘을 제공합니다. 결과: cATF의 크기가 문제 크기에 대해 최대 선형임을 증명합니다. SIPP의 특정 문제에 대한 구현체를 바탕으로 한 실험적 평가에 따르면, 어려운 문제에서 재계획(replanning)에 의존하는 에이전트는 실패하는 경우가 빈번한 반면, cATF를 사용하는 임의 시작 시간 알고리즘은 실행 시작 시간이 확정되면 최적 계획을 신속하게 조회할 수 있음을 보여줍니다. 결론: 시간 의존적 계획에 대한 효율적인 표현과 추론을 가능하게 함으로써, 본 연구는 동적 환경에서의 계획 수립을 위한 토대를 제공합니다.
추상 지시로부터 상식 기반 경로 계획
Commonsense-Grounded Path Planning from Abstract Instructions
우리는 추상적 지시를 상식을 따르는 경로로 바꾸는 새로운 경로 계획기인 \emph{commonsense ranked search}(CoRS)를 제안한다. 기존 방법은 사전에 명시된 고려사항은 반영하지만, 사람들 사이에서 일하는 로봇은 명시되지 않은 고려사항도 따라야 한다. 예를 들어 작업자가 지시 없이도 피하는 젖은 바닥이 그렇다. CoRS는 계획 과정에서 이러한 잠재적 고려사항을 추론하기 위해 대규모 언어 모델(LLM)과 비전-언어 모델(VLM)을 상식 지식으로 활용한다. 추상적 지시(\emph{e.g.}, ``move carefully'')와 환경의 각 영역에 대한 시각 관측이 주어지면, CoRS는 각 영역에 대한 고려사항을 도출한다. 예를 들어 ``this wet floor is slippery and worth a detour.''와 같다. 그다음 영역 간 고려사항을 비교하여 로봇이 둘 중 어느 쪽을 더 피해야 하는지 판단한다. 예를 들어 ``the crowd is worse than the wet floor.''와 같다. 이러한 판단은 영역들을 상식 순위로 정렬하고, 그 순위에서 나온 비용이 항상 유효한 경로를 반환하는 기존 탐색을 이끈다. 잠재적 고려사항 하에서의 계획을 위한 벤치마크를 구축했으며, 세 가지 환경, 1350개 문제, 세 단계 추상화 수준의 다섯 가지 지시를 포함한다. 실험 결과 CoRS는 명시되지 않은 고려사항을 발견하고, 우회할 가치가 있는 것은 돌아가며 나머지는 통과하는데, 이는 최근 LLM 기반 경로 계획기들이 달성하지 못하는 행동이다.
검증자가 정답을 유출할 수 있다: 폐루프 에이전트 디버깅에서 최적화에 앞선 진단 가능성
A Verifier Can Leak the Answer: Diagnosability Before Optimization in Closed-Loop Agent Debugging
에이전트(agent) 개발자들은 시뮬레이터 기반 검증자(verifier)를 통해 프롬프트, 도구, 정책 및 진단 알고리즘을 비교하는 방식을 점점 더 많이 활용하고 있습니다. 그러나 검증자는 솔버(solver) 비교를 무의미하게 만들 수도 있습니다. 즉, 검증자의 프로브(probe)나 술어(predicate)가 타깃의 식별 정보를 인코딩하고 있다면, 정확한 옵티마이저(optimizer)는 어떠한 실질적인 모호성도 해결하지 못한 채 효과적인 것처럼 보일 수 있습니다. 본 연구에서는 폐루프(closed-loop) 의사결정 에이전트를 위한 집계 트레이스 디버거에서 발생하는 이러한 실패 사례를 보고합니다. 정확한 최소 적중 집합(Minimum Hitting Set, MHS)과 전파 인식 탐욕 알고리즘(propagation-aware greedy method)은 12개 개발 사례 모두에서 동일한 지지 집합(support)을 반환했으며, 9/12 사례에서 동일한 주입 결함(planted fault) 복구를 달성했습니다. 후속 감사 결과, 정확한 앵커(exact-anchor) 술어가 9/9 사례에서 주입된 쌍을 생성한 것으로 확인되었습니다. 해당 앵커들을 제거한 후 전체 주입 쌍 복구율은 8/9였습니다. 그럼에도 불구하고 하드 프로브 싱글톤(hard-probe singleton) 쌍은 9/9 사례에서 주입된 쌍과 일치했으며, 전파 후 비어 있지 않은 잔여 충돌군(residual conflict family)이 유지된 사례는 전무했습니다(0/9). 옵티마이저는 올바르게 작동했으나, 검증자가 이미 정답을 노출하고 있었던 것입니다. 이에 본 논문에서는 솔버 우선 평가 방식을 지지 집합 기반 게이팅(support-gated) 검증 규약으로 대체합니다. 먼저 클린 참조 맵(clean reference map)을 통해 반복적인 컴포넌트 노출을 입증해야 하며, 그다음 일치된 참조/현재 게이트를 통해 비교 가능한 런타임 증거를 확립해야 하고, 그 이후에만 독립적으로 보정된 신호 규칙이 탐지 결과를 반환할 수 있습니다. 1,440개의 사례와 21,600개의 파티션 행으로 구성된 사전 등록된 홀드아웃(heldout) 평가에서, 55/72 체제-컴포넌트(regime-component) 단위가 참조 게이트를 통과했고, 54/55가 런타임 게이트를 통과했으며, 표현된 컴포넌트의 안정적 위허용(stable false admission)은 단측 정확 95% 상한선 0.1391과 함께 0/20을 기록했습니다. 승인된 단위 내에서는 영향을 받은 정상 트래픽이 공칭 결함 셀 비율(nominal fault-cell fraction)보다 탐지를 더 잘 예측했습니다. 본 연구의 핵심적인 구조적 교훈은 컴포넌트 선택기를 최적화하기 전에 증거의 적격성과 비공개성(non-revelation)을 먼저 검증해야 한다는 점입니다. 그렇지 않으면 더 강력한 솔버가 단지 더 강력한 검증자 아티팩트(artifact)를 인증하는 것에 불과할 수 있습니다.
복잡계 알고리즘 설계를 위한 환경으로서의 네트워크 월드 모델
Network World Models as Environments for Algorithm Design on Complex Systems
환경(environment)을 시뮬레이션하고 행동에 따라 환경이 어떻게 변화하는지 예측하는 월드 모델(world model)은 로보틱스와 같은 현실 세계 응용 분야에서 점점 더 많이 활용되고 있습니다. 복잡계 또한 행동의 효과가 즉각적으로 나타나지 않기 때문에 동일한 도구를 필요로 합니다. 캠페인을 위해 시드 노드를 설정하거나 전염병에 대비해 노드를 면역화하는 것은 그 자체만으로는 거의 변화를 일으키지 않으며, 중요한 것은 이후 단계들에 걸쳐 펼쳐지는 결과입니다. 특정 태스크에서 기대 성능을 극대화하도록 이러한 행동을 선택하는 알고리즘을 설계하는 것은 본질적으로 반복적인 과정이며, 모든 후보 알고리즘은 자신이 도출하는 결과에 따라 점수가 매겨져야 합니다. 이러한 결과를 얻는 작업은 시뮬레이션에 의존해 왔으나, 다수의 샘플링된 궤적(trajectory)에 걸쳐 후보들을 평가할 때 그 비용이 병목 현상을 유발합니다. 본 논문에서는 시간에 따른 개입 하에서 네트워크의 확산 역학을 학습하고, 각 행동을 네트워크에 적용하며, 그에 따른 결과를 예측하는 행동 조건부 네트워크 월드 모델을 제안합니다. 이 모델은 코딩 에이전트(agent)가 전체 롤아웃(rollout) 피드백, 행동 수준의 기여도(credit), 대안적 개입에 대한 반사실적 탐침(counterfactual probe)을 활용하여 실행 가능한 알고리즘을 설계하고 개선하는 알고리즘 설계 루프 내에서 고속 평가기 역할을 수행합니다. 8개의 네트워크 태스크와 5개의 확산 모델에 걸쳐, 설계된 알고리즘은 141개 설정 중 138개에서 보고된 가장 강력한 기준선(baseline)과 대등하거나 이를 능가하는 동시에 몬테카를로(Monte Carlo) 시뮬레이션 대비 최대 14.5배 빠른 롤아웃을 가능하게 합니다. 코드는 논문 채택 시 공개될 예정입니다.
SafeVantage: 신뢰할 수 있는 임바디드 의사결정을 위한 시점 인지 메모리
SafeVantage: Vantage-Aware Memory for Reliable Embodied Decisions
부분 관측성(partial observability) 환경에서 신뢰할 수 있는 임바디드(embodied) 의사결정을 내리려면 유의미한 관측과 충분한 뒷받침 증거가 필요합니다. 그러나 의미론적(semantic) 점수만으로는 어떤 시점(viewpoint)이 특정 주장을 뒷받침하는지, 또는 추가적인 증거를 어디서 확보해야 하는지 파악할 수 없습니다. 본 연구에서는 각 주장을 뒷받침하는 뷰, 카메라 포즈, 추정된 목표 위치를 보존하여 긍정적 지지(support)와 탐색 범위를 명확히 구분하는 시점 인지(vantage-aware) 의미 메모리 및 능동적 정보 획득 프레임워크인 SafeVantage를 소개합니다. 학습된 후보 관측 가능성(candidate-observability) 모델(model)은 주장 기반 지오메트리를 활용하여 도달 가능한 시점에서의 목표 가시성을 예측합니다. 이러한 예측은 이동 비용과 기하학적으로 구별되는 확증을 고려하여, 최종 결정 손실(loss)의 기대 감소량을 바탕으로 시점 선택을 유도합니다. 이후 보정된 헤드가 지지 증거, 공간적 일관성, 커버리지를 결합하여 'Yes', 'No', 또는 'Abstain(기권)' 결정을 내립니다. 저자들은 232개의 미확인 ProcTHOR 주택과 방법 및 행동 예산당 7,424개의 쌍을 이룬 에피소드에 걸친 범주 존재성 벤치마크(benchmark)에서 SafeVantage를 평가(evaluation)합니다. 검증(validation)을 통해 선정된 동일 예산의 베이스라인과 비교했을 때, SafeVantage는 8회 및 12회 행동 조건에서 각각 24.7%와 12.0%의 매크로-F1 향상을 달성하며, 두 예산 모두에서 더 낮은 위험과 더 높은 응답률을 기록했고 8회 행동 시 이동 거리를 31.7% 단축했습니다. 동일 입력 HM3D 실험에서는 고정 관측 환경에서 더 낮은 선택적 위험을 보였으며, 통제된 ScanNet 개입 실험을 통해 뒷받침 뷰를 복원하는 것이 다운스트림 VLM 응답을 개선함을 입증했습니다. 소거 연구는 후보 관측 가능성이 결정 품질과 정보 획득 효율성에 기여함을 추가로 뒷받침합니다. 본 결과는 의미 메모리, 능동적 정보 획득, 신뢰할 수 있는 의사결정을 연결하는 데 있어 주장 수준의 시점 증거가 지닌 가치를 보여줍니다. 코드는 https://safevantage.github.io 에서 확인할 수 있습니다.
필터링을 통한 LLM 기반 자율 웹 에이전트 성능 향상
Improving LLM-based Autonomous Web Agents with Filtering
대규모 언어 모델(LLM) 기반의 자율 웹 에이전트는 다단계 추론 및 의사결정 능력을 바탕으로 다양한 웹 기반 작업을 자동화하여 상당한 주목을 받아왔다. 이러한 에이전트 개발에서 미해결 연구 과제 중 하나는 웹페이지 입력의 형식이다. 방대하고 종종 무관한 세부 정보를 포함하는 원시 HTML 소스 코드는 제한된 컨텍스트 윈도우(context window)를 가진 LLM에 어려움을 초래한다. 이러한 문제를 해결하기 위해, 본 연구에서는 먼저 WebArena (Zhou et al., 2023) 벤치마크에서 GPT-3.5 및 LLaMA-2-70B와 같은 기준선(baseline) 모델들을 재현하여 공통적인 실패 양상을 식별한다. 그런 다음 LLM 에이전트를 위해 무관한 문맥을 걸러내는 두 가지 검색 전략을 제안한다. 작업과의 관련성에 따라 HTML 요소들의 순위를 매기는 DeBERTa 기반 및 T5 기반 모델을 개발한다. 이들을 Mind2Web 궤적 데이터에서 파인튜닝(fine-tuning)한 후 WebArena로 전이한다. 실험 결과, DeBERTa 기반 모델은 WebArena에서 LLaMA-2-70B LLM 에이전트의 성공률을 1.97%에서 2.96%로 향상시키는 것으로 나타났다. 나아가, Mind2Web에서 0.52, WebArena에서 0.47의 재현율(recall)로 정답 요소를 검색할 수 있는 제로샷(zero-shot) ColBERT 기반 리트리버를 개발한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.