Open Source Robotics

고품질 오픈소스 로봇 프로젝트, 도구 및 소프트웨어의 엄선된 컬렉션.

Hybrid A*

  • 다른 이름: Hybrid A-star, hybrid-state A*
  • 카테고리: Planning & manipulation › Motion planning
  • 태그: path-planning, graph-search, autonomous-driving, nonholonomic, parking

자동차형 로봇을 위한 A* 탐색의 변형으로, 연속 상태에서 실행 가능한 조향 움직임을 시뮬레이션해 노드를 확장하면서 거친 (x, y, 방향각) 격자로 가지치기를 한다.

정의

Hybrid A는 비홀로노믹 구속이 있는 차량을 위한 탐색 기반 경로 플래너로, Dolgov, Thrun, Montemerlo, Diebel이 2007년 DARPA Urban Challenge에 출전한 Stanford 팀을 위해 도입했으며, 그 대회에서 주차장과 그 밖의 비정형 구역을 담당했다. 표준 A와 마찬가지로 비용과 휴리스틱의 합으로 정렬된 열린 목록을 유지한다. 차이는 상태를 표현하는 방식에 있다. 탐색 공간은 위치와 방향각에 걸친 셀로 나뉘지만, 각 노드는 정확한 연속 자세를 유지한다. 노드는 보통 기구학적 자전거 모델**로 차량을 시뮬레이션하여 확장하는데, 왼쪽 최대, 직진, 오른쪽 최대처럼 몇 가지 조향각으로 짧은 호를 따라 전진하고, 허용된다면 후진도 한다. 새 자세는 그 셀에 더 낮은 비용으로 이미 도달한 적이 없을 때에만 유지된다.

모든 간선이 시뮬레이션된 움직임이므로, 결과 경로는 구성상 주행 가능하며, 이는 셀 중심 위에서 돌리는 평범한 격자 A가 줄 수 없는 성질이다. 그 대가로 셀 단위 가지치기가 해로 이어질 수도 있었던 상태를 버리므로, 이 플래너는 엄밀한 의미에서 완전하지도 최적이지도 않다. 셀이 거칠면 빠르지만 빡빡한 기동을 놓칠 수 있다. 원래 방법은 허용 가능한 휴리스틱 두 개를 쓰고 더 큰 값을 택했다. 하나는 Reeds–Shepp 경로나 Dubins 자동차** 경로처럼 장애물이 없을 때 자동차의 최단 경로 길이이고, 다른 하나는 격자 위 2D 탐색으로 구한, 제자리에서 회전할 수 있는 로봇의 장애물을 고려한 최단 경로이다. 또한 주기적으로 현재 노드를 Reeds–Shepp 곡선으로 목표에 직접 연결해 보았는데, 이를 해석적 확장(analytic expansion)이라 하며, 탐색이 정확한 목표 자세에 도달하는 데 도움이 된다.

원시 경로는 이산적인 조향 선택을 따르므로 약간 지그재그로 흔들린다. 원래 시스템은 여유 거리, 곡률, 매끄러움의 균형을 맞추는 경사 기반 최적화기로 이를 평활화한 다음, 추종 제어기를 위해 보간했다. Hybrid A는 미리 계산한 모션 프리미티브**로 고정된 래티스 점들을 연결하는 상태 래티스 계획과도 다르고, 기준 차선을 가정하는 Frenet 좌표계 플래너와도 다르다.

중요한 이유

Hybrid A*는 주차장, 야드 등 차선이 없는 공간에서 자동차형 로봇에 가장 널리 쓰이는 플래너 중 하나이다. 격자 탐색의 속도와 차량의 회전 한계를 지키는 경로를 결합하는 실용적인 방법을 보여 주며, 그 구조는 여러 오픈소스 주행 스택에 나타난다.

주요 응용

  • 자동 주차와 발레 기동
  • 야드와 차고지에서의 트럭, 견인차, 트레일러 기동
  • 창고, 농장, 건설 현장의 자동차형 로봇
  • 자율주행 스택의 비정형 구역 계획
  • 오프로드 및 광산 차량의 경로 계획

실제 사례

한 자율 견인차가 후진으로 하역장에 들어가야 한다. 플래너는 야드를 위치 셀과 방향각 구간으로 이산화하고, 자전거 모델을 써서 전진과 후진의 몇 가지 조향각으로 노드를 확장하며, 시뮬레이션된 각 자세에서 차량의 외곽 전체(footprint)가 충돌하는지 검사한다. 몇 번 확장할 때마다 하역장 자세로 향하는 직접적인 Reeds–Shepp 연결을 시도한다. 경로를 찾으면 곡률과 여유 거리에 대해 평활화하고, 충돌을 다시 검사하고, 속도 프로파일을 붙인 뒤 경로 추종 제어기가 이를 주행한다. 빡빡한 곳에서 플래너가 실패하면, 팀은 다른 것을 바꾸기 전에 먼저 셀 크기를 줄이거나 조향각을 더 추가한다.

흔한 오해

  • Hybrid A는 격자 위의 일반 A이다 — 노드는 시뮬레이션된 조향 움직임으로 도달한 연속 자세를 저장하며, 격자는 중복을 가지치기하는 데만 쓰인다
  • 격자 때문에 경로가 기구학적으로 실행 불가능할 수 있다 — 간선이 시뮬레이션된 차량 움직임이므로 실행 가능성은 유지된다. 격자가 대가로 치르는 것은 완전성과 최적성이다
  • Hybrid A*는 최단 경로를 준다 — 셀 가지치기와 제한된 조향 선택 때문에 결과는 근사적이며, 보통 평활화가 뒤따른다
  • 속도까지 포함한 전체 궤적을 계획한다 — 기하학적 경로를 계획하며, 속도 프로파일과 동역학은 그 뒤에 처리한다

알아야 할 사람

  • 주차와 비정형 구역을 다루는 자율주행 엔지니어
  • 자동차형 또는 애커먼 플랫폼을 쓰는 이동 로봇 개발자
  • 탐색 기반 계획을 공부하는 모션 플래닝 학생
  • 농업, 광업, 물류 분야의 필드 로보틱스 엔지니어

관련 기술

  • A* 탐색
  • Reeds–Shepp 곡선
  • 상태 래티스 플래너(state lattice planner)
  • 보로노이 필드(Voronoi field)
  • 경로 평활화
  • Pure pursuit와 Stanley 제어기

관련 용어

  • Nonholonomic Constraint
  • Dubins Car
  • Bicycle model
  • Motion Primitive
  • Configuration Space
  • Frenet Frame Planning

관련 프로젝트

  • Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
  • ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
  • OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
  • Mesh Navigation: Robot navigation on 3D triangle meshes for rough outdoor terrain, from Nature Robots
  • Fields2Cover: Coverage path planning library for autonomous agricultural vehicles
  • Vision Pilot: Autoware Foundation's open-source L2 ADAS stack from a single camera

이 웹사이트는 JavaScript가 필요합니다. 오픈소스 로봇 프로젝트를 탐색하려면 JavaScript를 활성화하세요.