Path Planning이란?

Path Planning을 사용하면 자율주행 차량 또는 로봇이 시작 상태부터 목표 상태까지 장애물이 최대한 없는 최단 경로를 찾도록 할 수 있습니다. 경로는 상태(위치 및/또는 방향) 또는 중간점의 집합일 수 있습니다. Path Planning에는 환경의 지도 및 입력값으로 사용할 시작 상태와 목표 상태가 필요합니다. 지도는 그리드 지도, 상태공간, 위상 로드맵 등 다양한 방식으로 표현할 수 있습니다. 지도를 다중 계층으로 만들면 경로에 편향을 추가할 수 있습니다.

자율주행 차량에 널리 사용되는 몇 가지 Path Planning 알고리즘의 범주는 다음과 같습니다.

• 그리드 기반 탐색 알고리즘: 그리드 지도에서 최소 이동 비용을 갖는 경로를 찾습니다. 2차원 환경의 이동 로봇 같은 응용 분야에 사용할 수 있습니다. 그러나 그리드 기반 알고리즘 구현에 필요한 메모리 요구량은 차원 수에 따라 늘어날 수 있습니다. 6-DOF 로봇 매니퓰레이터를 예로 들 수 있습니다.
• 샘플링 기반 탐색 알고리즘: 상태공간에서 새로운 노드나 로봇 형상을 임의로 샘플링하여 탐색 가능한 트리를 생성합니다. 샘플링 기반 알고리즘은 로봇 팔이 물체를 집어 들 수 있는 유효한 형상 집합을 찾는 데 사용되는 것과 같은 고차원 탐색 공간에 적합할 수 있습니다. 샘플링 기반 계획은 완전해를 제공하지는 않더라도 다양한 실제 응용 사례에 맞게 동적으로 실현 가능한 경로를 생성한다는 점에 힘입어 널리 쓰이고 있습니다.
• 궤적 최적화 알고리즘: Path Planning 문제를 원하는 차량 성능, 관련 제약 조건, 차량 동역학을 고려하는 최적화 문제로 정식화합니다. 이 알고리즘은 동적으로 실현 가능한 궤적을 생성하는 것 외에, 불확실한 환경에서의 온라인 Path Planning에도 적용할 수 있습니다. 그러나 최적화 문제의 복잡도에 따라 실시간 계획은 비용이 매우 클 수 있습니다.

Path Planning과 인식(또는 비전) 및 제어 시스템은 모든 로봇 또는 자동차의 자율 내비게이션을 이루는 세 가지 주요 구성 요소입니다. Path Planning은 자율주행 자동차, 로봇 매니퓰레이터, UGV(무인 지상 차량), UAV(무인 항공기) 등의 시스템에 자율성을 더해줍니다.

MATLAB^®, Simulink^®, Navigation Toolbox™ 및 Model Predictive Control Toolbox™에서 제공하는 Path Planning 툴을 사용하여 다음과 같은 작업을 할 수 있습니다.

• 사용자 지정 가능한 계획 인프라를 사용하여 RRT 및 RRT* 같은 샘플링 기반의 Path Planning 알고리즘 구현
• Hybrid A* 를 사용하여 자동 주차와 같은 점유 그리드 지도의 경로 계획
• 실내 동적 재계획 및 자동 고속도로 차선 변경을 위한 국소 궤적 생성
• 평활도, 회피 간격 같은 경로 메트릭을 사용하여 경로 유효성과 최적성 비교
• 중간점을 생성하고 순수 추종 제어기를 사용하여 중간점을 따라가도록 제어 명령 전송
• 선형 및 비선형 모델 예측 제어를 통해 온라인 Path Planning을 위한 동적 실현 가능 궤적의 생성 및 따름
• Simulink에서 Vehicle Path Planner System 블록으로 충돌 회피 궤적 계획
• Path Planning 알고리즘을 독립형 ROS 노드 또는 C/C++ 코드로 임베디드 플랫폼에 배포