arXiv:1904.02341

Online Risk-Bounded Motion Planning for Autonomous Vehicles in Dynamic Environments

Xin Huang, Sungkweon Hong, Andreas Hofmann, Brian C. Williams

제출 2019-04-04

원문 초록

A crucial challenge to efficient and robust motion planning for autonomous vehicles is understanding the intentions of the surrounding agents. Ignoring the intentions of the other agents in dynamic environments can lead to risky or over-conservative plans. In this work, we model the motion planning problem as a partially observable Markov decision process (POMDP) and propose an online system that combines an intent recognition algorithm and a POMDP solver to generate risk-bounded plans for the ego vehicle navigating with a number of dynamic agent vehicles. The intent recognition algorithm predicts the probabilistic hybrid motion states of each agent vehicle over a finite horizon using Bayesian filtering and a library of pre-learned maneuver motion models. We update the POMDP model with the intent recognition results in real time and solve it using a heuristic search algorithm which produces policies with upper-bound guarantees on the probability of near colliding with other dynamic agents. We demonstrate that our system is able to generate better motion plans in terms of efficiency and safety in a number of challenging environments including unprotected intersection left turns and lane changes as compared to the baseline methods.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2610.03312v1cs.AI공통 태그 Motion Planning, Heuristic Search

동적 환경에서의 최적 계획 수립

Optimal Planning in a Dynamic World

배경: 본 논문에서는 실행 가능한 상태나 행동의 집합이 시간에 따라 변하는 환경에서의 계획 수립(planning) 문제를 다룹니다. 예를 들어, 이동하는 장애물 사이에서의 경로 계획 문제(흔히 SIPP로 알려짐)에서는 장애물이 이동함에 따라 특정 위치에 머무를 수 있는 가능 여부가 달라질 수 있습니다. 또는 특정 기차에 탑승하는 행동은 기차가 역에 정차해 있는 동안에만 실행 가능합니다. 이러한 동적 특성으로 인해 최적 계획과 그 수행 시간은 실행이 언제 시작되는지에 따라 달라질 수 있습니다. 실제 환경에서는 계획 수립이 완료되거나 다른 에이전트(agent)의 승인이 날 때까지 실행 시작 시간을 알 수 없는 경우가 많습니다. 그러나 기존의 계획 수립 연구 대부분은 이러한 동적 특성을 무시하거나 시작 시간이 사전에 알려져 있다고 가정합니다. 이는 상태와 행동의 실행 가능성을 평가하기는 수월하게 만들지만, 일부 응용 분야에서는 비현실적입니다. 목표: 본 논문에서는 시작 시간이 알려져 있다는 가정을 완화합니다. 임의 시작 시간 계획 수립(any-start-time planning) 설정을 정의하고 이를 위한 알고리즘을 제시합니다. 방법: 시작 시간의 함수로서 최적 계획을 간결하게 인코딩하는 복합 도착 시간 함수(compound arrival time function, cATF)라는 자료구조를 제안합니다. 또한 스칼라 비용 대신 간선을 따라 함수를 전파하여 cATF를 구성하는, 휴리스틱 그래프 탐색 기반의 범용 계획 수립 알고리즘을 제공합니다. 결과: cATF의 크기가 문제 크기에 대해 최대 선형임을 증명합니다. SIPP의 특정 문제에 대한 구현체를 바탕으로 한 실험적 평가에 따르면, 어려운 문제에서 재계획(replanning)에 의존하는 에이전트는 실패하는 경우가 빈번한 반면, cATF를 사용하는 임의 시작 시간 알고리즘은 실행 시작 시간이 확정되면 최적 계획을 신속하게 조회할 수 있음을 보여줍니다. 결론: 시간 의존적 계획에 대한 효율적인 표현과 추론을 가능하게 함으로써, 본 연구는 동적 환경에서의 계획 수립을 위한 토대를 제공합니다.

arXiv:2508.19186v2cs.RO공통 태그 Autonomous Vehicles, Motion Planning

폐루프 로봇 반응형 계획을 위한 실시간 모델 체킹

Real-Time Model Checking for Closed-Loop Robot Reactive Planning

반응형 장애물 회피 방법은 종종 한 단계 앞만(즉, 현재 상태에 기반한 다음 행동만) 추론할 수 있기 때문에 에이전트가 국소 최솟값(local minima)에 갇히게 한다. 본 논문에서는 자율 로봇에서 반응형 다단계 계획과 장애물 회피를 달성하기 위해 모델 체킹을 사용한다. 우리의 소규모 맞춤형 모델 체킹 알고리즘은 생물학적 에이전트에서 발견되는 '핵심(core)' 지식과 어텐션에 기반하여 로봇 코드 내 현장(in situ)에서 계획을 생성한다. 이는 사전 계산된 데이터 없이 저전력 장치에서 실시간으로 달성된다. 우리의 접근법은 자율 에이전트가 선호하는 행동(또는 안정 상태)을 방해하는 국소 환경의 교란에 대응하기 위해 생성되는 임시 제어 시스템들을 연쇄적으로 연결하는 것에 기반한다. 우리는 즉각적 환경의 임시 스냅샷에 의존하고 상태 수를 제한함으로써 상태 공간 폭발(state-space explosion)을 완화한다. 깊이 우선 탐색(depth-first search)과 부정된 LTL(Linear Temporal Logic) 경로 속성에 의해 생성된 반례(counter-examples)를 사용한 다단계 계획은 막다른 골목(cul-de-sac)과 독립형 장애물 시나리오에 적용된다. 실험 결과와 두 가지 기본 속성에 대한 비공식 증명은 국소 장애물 회피를 위한 효율적인 다단계 계획 생성에서 우리 접근법의 효과를 보여준다. 우리는 한 단계 앞만 계획할 수 있는 순수 반응형 에이전트와 비교하여 성능을 크게 개선한다. 우리의 접근법은 자율 주행 차량 맥락에서 안전하고 신뢰할 수 있는 내비게이션 개발을 위한 교육적 사례 연구이다. 또한 임무에 중요한(mission-critical) 이동 로봇의 내비게이션에도 일반적으로 적용될 수 있다고 우리는 믿는다.

arXiv:2606.06531v1cs.AI공통 태그 Autonomous Vehicles, Motion Planning

CARVE-Q: 양자 제안, 고전 인증 대화형 주행 수리

CARVE-Q: Quantum-Proposed, Classically Certified Interactive Driving Repair

올바른 주행 거부(veto) 이후의 핵심 질문은 기동(maneuver)이 안전하지 않은지 여부뿐만 아니라, 차단된 상호작용이 합법적이고 감사 가능하며 책임 범위가 제한된 수리를 허용하는지 여부이다. 예측 및 게임 이론적 플래너(planner)는 그럴듯한 협력을 제안할 수 있지만, 수리가 엄격한 규칙, 우선통행권(right-of-way), 비용 배분, ego 전용 폴백(fallback)을 준수한다는 증명을 반환하지는 않는다. 우리는 CARVE(Certified Affordable Repair of Vetoed maneuvers via Envelopes)를 소개한다. 이는 예측 없는(prediction-free) 대화형 수리를 위한 인증(certificate) 아키텍처이다. 거부된 기동이 주어지면, CARVE는 유한한 수리 격자(lattice)를 구성하고, 구속 규칙, 선택된 공동 수리, 우선통행권 스케일 협력 포락(envelope), 책임 가중 비용 분배, ego 전용 폴백을 기록하는 구조화된 인증을 출력한다. 이 인증 관점은 알고리즘적 병목을 드러낸다: 다중 소유자 수리는 곱 격자 $M = \prod_j |\mathcal{A}_j|$를 유도한다. 따라서 우리는 CARVE-Q를 도입한다. 이는 검증자 보호(verifier-shielded) 양자-AI 탐색 층(layer)으로, 이 블랙박스 격자에만 양자 최솟값 탐색(minimum finding)을 적용하면서 모든 안전성 권한은 고전적으로 유지한다. 보수적 검증자-오라클(verifier-oracle) 모델에서, 정확한 고전 최솟값 탐색은 최악의 경우 $Θ(M)$ 쿼리를 필요로 하는 반면, Durr-Hoyer/Grover 최솟값 탐색은 높은 확률로 $O(\sqrt{M})$ 오라클 쿼리를 사용한다. 우리는 검증자 보호 인증 건전성(soundness), 우선순위 비유출(non-elicitation), 블랙박스 쿼리 분리, 유한 정밀도(finite-precision) 가역 오라클 구성 가능성(constructibility)을 증명한다. 이어서 CARVE 수리 오라클에 대해 최대 65,536개 할당까지 상태 벡터(state-vector) 최솟값 탐색을 시연하고, Lanelet2 기반 INTERACTION 리플레이에서 인증 보존을 검증한다. 우선통행권 준수 100%, 책임(blame) 일관성 100%, 우선순위 위양성(false positive) 0건을 달성했다. 그 결과는 인증된 자율주행(autonomy)을 위한 신뢰 경계(trust-bounded) 양자-AI 패턴이다: 양자가 제안하고, CARVE가 인증한다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.