경로탐색 알고리즘 기술 개발 | KAIST 모빌리티AX연구소

경로 계획 (Path planning)은 로보틱스, 자율주행, 무인항공기(UAV), 그리고 가상환경의 에이전트 시뮬레이션에 이르기까지 지능형 자율 시스템의 가장 근본적이고 핵심적인 문제임.
해당 문제는 출발지에서 목적지까지 최소 비용으로 도달하는 경로를 도출하는 문제이며, 정적·동적 장애물을 회피하면서 이동 시간, 에너지 소모량, 안전 거리 등 복수의 기준을 동시에 만족해야 하는 다목적 최적화 문제임.
특히, 돌발 상황이 빈번한 실제 주행 환경에서는 제한된 컴퓨팅 자원으로 대안 경로를 즉시 재산출해야 하므로, 알고리즘의 실시간 연산 효율성과 탐색의 강건성 확보가 중요함.

본 연구는 대상 네트워크를 1) 전기 회로적 관점에서 해석하여 단일 혹은 다중 경로 계획 문제를 풀이하고, 2) 대규모, 복잡한 네트워크에서도 연결성이 보장된 경로를 효율적으로 도출하는 방법을 제안하고자 함.

본 연구는 도로 네트워크와 전기 회로 간의 상사성에 착안하여, 대상 네트워크를 전기 저항 네트워크 형태의 등가 회로로 모델링하여 분석함.
구성된 회로에 회로 이론의 법칙을 적용하여 목적에 맞는 최적의 전류 분포를 도출함.
전류는 저항이 작은 구간으로, 최적 경로는 비용이 적은 링크를 선택한다는 점에서 유사함. 이에 따라 최적 전류 분포와 최적 경로 간의 상관성이 성립함.

본 연구는 주행 네트워크를 전기 회로 관점에서 해석하여, 간단한 회로 분석과 후처리 만으로도 사용자 제약(경유지 방문, 구역 회피 등)을 만족하는 단일/다중 경로를 도출함.
대규모 네트워크에서도 적은 연산 비용으로 최적에 준하는 해를 도출하며, 실효성 높은 경로를 실시간으로 제공함.
해석 결과가 이미지 형태의 데이터이므로, 별도의 전처리 없이 딥러닝 모델과 즉시 연동 가능함.