원문 초록
Any-angle path planning extends traditional graph-based path planning by allowing movement between any pair of vertices, rather than being restricted by predefined edges. It can find straighter and shorter paths in continuous space with graphs, making it particularly suitable for navigation in open areas such as airspaces, warehouses, and oceans. Many any-angle path-planning algorithms have been proposed, but only a few can guarantee optimal solutions, especially in the presence of dynamic obstacles. To address this challenge, this article focuses on optimal any-angle path planning on grids and introduces two general techniques that accelerate computation while preserving optimality in both static and dynamic environments: 1) elliptical forward expansion, which leverages ellipse-based neighborhoods to restrict the search space, and 2) field of view, which replaces traditional line-of-sight methods to speed up visibility checks. To integrate these two techniques, inverted and forward scanning are introduced. Inverted scanning establishes visual connections from open nodes, whereas forward scanning initiates scans from closed nodes. Building on the proposed techniques, Zeta* and Zeta*-SIPP are developed for static and dynamic environments respectively. Zeta*, when combined with forward scanning, is similar to the state-of-the-art algorithm Anya and attains comparable performance. Unlike Anya, Zeta* can be readily extended to other settings, such as dynamic environments (e.g., Zeta*-SIPP). Zeta*-SIPP, with either scanning method, is more than 20 times faster than the corresponding state-of-the-art optimal planner TO-AA-SIPP. Overall, this research identifies the key requirements for achieving optimal any-angle path planning and introduces a unified approach suitable for different environments.
요약
정적 및 동적 환경에서의 최적 임의각도 경로 계획(any-angle path planning)을 위해 타원 기반 전방 확장(elliptical forward expansion)과 시야각(field of view) 기법을 도입하여 최적성을 유지하면서 탐색 공간과 가시성 검사를 가속화하는 두 가지 핵심 기술을 제안한다. 이를 기반으로 개발된 Zeta*는 정적 환경에서 최신 알고리즘 Anya와 유사한 성능을 달성하며, Zeta*-SIPP는 동적 환경에서 최신 최적 계획기 TO-AA-SIPP 대비 평균 20배 이상의 속도 향상을 보인다.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2607.00065v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
동적 환경에서의 최적 계획 수립
Optimal Planning in a Dynamic World
배경: 본 논문에서는 실행 가능한 상태나 행동의 집합이 시간에 따라 변하는 환경에서의 계획 수립(planning) 문제를 다룹니다. 예를 들어, 이동하는 장애물 사이에서의 경로 계획 문제(흔히 SIPP로 알려짐)에서는 장애물이 이동함에 따라 특정 위치에 머무를 수 있는 가능 여부가 달라질 수 있습니다. 또는 특정 기차에 탑승하는 행동은 기차가 역에 정차해 있는 동안에만 실행 가능합니다. 이러한 동적 특성으로 인해 최적 계획과 그 수행 시간은 실행이 언제 시작되는지에 따라 달라질 수 있습니다. 실제 환경에서는 계획 수립이 완료되거나 다른 에이전트(agent)의 승인이 날 때까지 실행 시작 시간을 알 수 없는 경우가 많습니다. 그러나 기존의 계획 수립 연구 대부분은 이러한 동적 특성을 무시하거나 시작 시간이 사전에 알려져 있다고 가정합니다. 이는 상태와 행동의 실행 가능성을 평가하기는 수월하게 만들지만, 일부 응용 분야에서는 비현실적입니다. 목표: 본 논문에서는 시작 시간이 알려져 있다는 가정을 완화합니다. 임의 시작 시간 계획 수립(any-start-time planning) 설정을 정의하고 이를 위한 알고리즘을 제시합니다. 방법: 시작 시간의 함수로서 최적 계획을 간결하게 인코딩하는 복합 도착 시간 함수(compound arrival time function, cATF)라는 자료구조를 제안합니다. 또한 스칼라 비용 대신 간선을 따라 함수를 전파하여 cATF를 구성하는, 휴리스틱 그래프 탐색 기반의 범용 계획 수립 알고리즘을 제공합니다. 결과: cATF의 크기가 문제 크기에 대해 최대 선형임을 증명합니다. SIPP의 특정 문제에 대한 구현체를 바탕으로 한 실험적 평가에 따르면, 어려운 문제에서 재계획(replanning)에 의존하는 에이전트는 실패하는 경우가 빈번한 반면, cATF를 사용하는 임의 시작 시간 알고리즘은 실행 시작 시간이 확정되면 최적 계획을 신속하게 조회할 수 있음을 보여줍니다. 결론: 시간 의존적 계획에 대한 효율적인 표현과 추론을 가능하게 함으로써, 본 연구는 동적 환경에서의 계획 수립을 위한 토대를 제공합니다.
로봇 내비게이션을 위한 최소 장애물 변위 계획의 호리즌 슬라이싱 접근법
A Horizon-slicing Approach to Minimum Obstacle Displacement Planning for Robot Navigation
본 논문에서는 로봇 동작 계획(motion planning) 관점에서 최소 장애물 변위 계획(Minimum Obstacle Displacement Planning) 문제를 다룬다. 이 문제는 처음에 충돌 없는 경로가 없을 때 이동 가능한 장애물을 변위시켜 목표 지점까지의 실행 가능한 경로를 찾는 것을 포함한다. 우리는 이 문제가 계산적으로 어렵고, 특히 장애물을 평면상의 다각형으로 모델링할 때 NP-hard임을 보인다. 문헌의 다른 문제들을 일반화하는 최소 장애물 변위 문제의 정확한 공식화와 이에 대응하는 최적해 외에, 본 논문은 계산 부담이 더 적은 근사해를 제안하며, 이는 최적해와 최적 비용의 일부만큼만 차이 나며, 경로 길이와 장애물 변위량 사이의 트레이드오프를 조절할 수 있다.
체계적 다중 에이전트 비전-언어 내비게이션: 공식화, 벤치마크 및 방법론
Systematic Multi-Agent Vision-and-Language Navigation: Formulation, Benchmark, and Method
비전-언어 내비게이션(VLN)은 주로 단일 에이전트가 단일 지시를 따르는 데 초점을 맞추어 왔으나, 많은 실제 응용 분야에서는 개별 에이전트의 역량을 넘어서는 작업을 해결하기 위해 로봇 팀을 필요로 합니다. 본 연구에서는 체계적 다중 에이전트 비전-언어 내비게이션을 제시하며, 우리가 아는 한 다중 에이전트 VLN을 제약 조건이 있는 협업 문제로 최초 체계적으로 공식화합니다. 각 임무는 의존성 및 자원 제약(존재 잠금 및 유지 체인)을 수반하는 하위 작업으로 구성됩니다. 검증된 4단계 제작 파이프라인을 통해 세 가지 지시 체제 하에서 최대 4개의 에이전트로 구성된 팀과 함께 145개 장면에 걸친 11,724개 에피소드로 이루어진 MAVLN으로 작업을 인스턴스화하고, 맞춤형 제약 인식 지표를 함께 제공합니다. 나아가 대규모 언어 모델(LLM) 기반 하위 작업 스케줄러, 각 에이전트의 탐험을 팀 지식으로 전환하는 공유 위상학적 메모리, 그리고 동시 의도를 충돌 없는 경로로 구현하는 충돌 인식 실행 메커니즘을 결합한 협업 지원 내비게이션 시스템인 TRISS를 제시합니다. 광범위한 실험을 통해 TRISS가 포괄적인 기준선임을 입증하며, 스케줄링, 계획, 실행 전반에 걸쳐 상당한 개선 여지가 있음을 밝혀 MAVLN 작업 제약 하에서의 협업 과제를 부각합니다. 프로젝트 페이지: https://xyz9911.github.io/mavln.
DeliveryGym: An RL Environment for Long-Horizon Embodied Agent Planning with Adaptive Curriculum
The user asked for a JSON-only translation response with no markdown fences. Here is the result: {"title_ko": "DeliveryGym: 적응형 커리큘럼 기반 장기 체화 에이전트 계획을 위한 강화학습 환경", "abstract_ko": "실행 가능한 환경은 LLM 에이전트가 자신의 행동 결과로부터 학습할 수 있게 한다. 체화 에이전트의 경우, 그 결과는 현재 과제의 성공 여부를 넘어선다. 배달을 완료하는 것은 이후 작업에 필요한 시간, 에너지, 또는 돈을 소모할 수 있다. 따라서 계획 학습을 위해서는 이러한 의존성을 보존하고 완전한 궤적에 걸쳐 이를 피드백으로 전환하는 환경이 필요하다.\n\n우리는 연속적인 배달원 근무 교대를 대상으로 에이전트를 평가하고 학습하는 3D 환경인 DeliveryGym을 제안한다. 이는 다중 모달 도구 상호작용과 지속적인 세계 동역학을 결합하고, 시뮬레이터 이벤트로부터 궤적 보상을 계산하여 에이전트 결정의 비용을 강화학습(RL)에 사용할 수 있게 한다. 또한 평가는 고정한 채, 환경은 정책에서 관찰된 약점에 맞춰 향후 학습 교대를 적응시킨다.\n\n6개 모델과 13개 도시 맵에 걸쳐, 평가는 할당된 배달을 안정적으로 수행하는 것과 한 교대 동안 업무를 선택하고 순서를 정하는 것 사이의 격차를 드러낸다. 보지 못한 도시 테스트 세트에서 RL은 Qwen3-VL-4B의 순수익을 54.3% 향상시켜, 완전한 교대로부터 학습하면 이러한 결합된 제약 하에서 성능이 개선됨을 보여준다. 학습 환경을 적응시키면 100회 업데이트에서 균일 샘pling 대비 평가 수익이 18% 개선되어, 에이전트가 연습하는 상황이 무엇인지도 중요함을 시사한다. DeliveryGym은 에피소드 내에서 배달을 조율하고 이후 주문을 위해 자원을 보존하는 방법을 에이전트가 학습하는 과정을 연구할 수 있는 실행 가능한 설정을 제공한다."}
추상 지시로부터 상식 기반 경로 계획
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 기반 경로 계획기들이 달성하지 못하는 행동이다.
명시적 3D 재구성 없이 이미지로부터 직접 수행하는 6-자유도(6-DoF) 궤적 계획을 위한 SE(3) 신경 포텐셜 필드
SE(3) Neural Potential Fields for 6-DoF Trajectory Planning Directly from Images Without Explicit 3D Reconstruction
어수선한 환경(clutter)에서 6-자유도(6-DoF) 파지 자세(grasp pose)에 도달하려면 충돌이 없는 궤적이 필요하며, 기존에는 장면을 3D로 재구성하고 그 재구성 안에서 계획을 수립하는 방식으로 이를 얻었으나, 이는 정확도와 연산 비용을 대가로 치른다. 이미지로부터 직접 학습된 포텐셜 필드(potential field)는 이러한 의존성을 제거하지만, 인공 포텐셜 필드(artificial potential field)의 고전적인 약점을 그대로 물려받는다: 인력(attractive)과 척력(repulsive) 기울기(gradient)가 상쇄되는 지점에서 하강 경로가 장애물을 우회하지 못하고 스치듯 지나가며, 목표에 도달하지 못하고 정체될 수 있다. 우리는 자세가 주어진(posed) RGB 이미지로부터 학습되고, 학습 중 동일한 이미지로부터 복원한 자유 공간(free space)을 통과하는 파지점까지의 측지 거리(geodesic distance)인 내비게이션 함수(navigation function)로 지도(supervise)되는 SE(3) 신경 포텐셜 필드를 제시하며, 이는 두 가지 실패 모두를 제거한다. 두 개의 테이블탑 장면에서, UR10 로봇으로 실행한 장애물로 막힌 시작 지점들로부터, 이 필드는 모든 시작 지점에서 파지점 3cm 이내로 수렴하며 실행되는 모든 경로가 실제 정답(ground-truth) 기하 구조에 대해 충돌이 없는 반면, 이미지 지도만 사용한 경우는 각각 25%와 0%에 그친다. 평균 여유 거리(clearance)는 1cm 미만에서 8.6-8.8cm로 상승하고, 로봇팔 링크 접촉은 실행된 구성(configuration)의 20.6-50.4%에서 2.7-5.5%로 감소한다. 실제 실행된 파지 성공률은 두 장면에서 각각 90.0%와 40.0%이며, 남은 실패는 필드가 아니라 데카르트 실행기(Cartesian executor)의 거부에 기인한다. 계획 수립에는 약 2초가 소요되는데, 동일한 이미지의 재구성에 대한 RRT*의 67-133초와 비교된다. 다만 공통의 오프라인 실험 환경(harness)에서는 두 방법이 비슷한 수준이며, 실제 배포 시 발생하는 마진(margin)은 계획기(planner)의 복잡도가 아니라 밀집 재구성(dense reconstruction)에 대한 충돌 검사 비용에서 비롯된다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.