경로 계획에 대한 종합적인 세부 정보

경로 계획은 모션 계획의 주요 연구 내용 중 하나입니다. 모션 계획은 경로 계획과 궤적 계획으로 구성됩니다. 시작 위치와 끝 위치를 연결하는 일련의 점 또는 곡선을 경로라고 하며 경로를 구성하는 전략을 경로 계획이라고 합니다.

경로 계획은 다양한 분야에서 널리 사용됩니다. 첨단 기술 분야의 응용 분야에는 로봇의 자율적 비충돌 동작, 드론의 장애물 회피 및 침투 비행, 레이더 탐색 회피, 반동 공격 방지, 침투 및 폭파 임무 등이 포함됩니다. 일상생활에서의 응용에는 GPS 네비게이션, GIS 시스템을 기반으로 한 도로 계획, 도시 도로망 계획 및 네비게이션 등이 포함됩니다. 의사결정 관리 분야의 적용에는 물류 관리의 차량 문제(VRP) 및 유사한 자원 관리 자원 할당 문제가 포함됩니다. 통신기술 분야의 라우팅 문제 등 기본적으로 점선 네트워크가 될 수 있는 토폴로지를 갖는 모든 계획 문제는 경로 계획 방법으로 해결할 수 있습니다. 기본 소개 중국어 이름: 경로 계획 외국 이름: 경로 계획 범주: 전자 정보 기술 응용 분야: 첨단 기술, 일상 생활, 물류 관리 등 공통 알고리즘: Dijkstra 알고리즘, 유전 알고리즘 및 기타 경로 계획 문제 분류, 일반적인 경로 단계 계획, 일반적으로 사용되는 알고리즘, 기존 알고리즘, 그래픽 방법, 지능형 생체 공학 알고리즘, 경로 계획 응용, 이산 영역의 최단 경로 계획 문제, 이산 영역의 에르고딕 최적 경로 문제, 연속 영역의 전역 경로 계획 문제, 로컬 경로 계획 연속 영역 내 문제, 연속 영역 내 에르고딕 경로 계획 문제, 경로 계획의 향후 개발, 경로 계획 문제의 분류 경로 계획은 환경 정보의 파악 정도에 따라 선험적 경로 계획으로 나눌 수 있습니다. 완전한 정보를 통한 계획과 센서 정보를 기반으로 한 지역 경로 계획. 그 중 장애물 정보 획득이 정적인지 동적인지의 관점에서 볼 때 전체 경로 계획은 정적 계획(오프라인 계획이라고도 함)에 속하고 로컬 경로 계획은 동적 계획(온라인 계획이라고도 함)에 속합니다. 전역 경로 계획은 모든 환경 정보를 숙지하고 환경 지도의 모든 정보를 기반으로 경로를 계획하는 것이 필요하며, 로컬 경로 계획은 센서를 통해 환경 정보를 실시간으로 수집하고 환경 지도 정보를 이해한 후 위치를 결정하는 것만 필요합니다. 지도와 지역 특성을 파악하여 현재 노드에서 특정 하위 대상 노드까지의 최적 경로를 선택할 수 있습니다. 연구 대상 환경의 정보 특성에 따라 경로 계획은 이산 영역의 경로 계획 문제와 연속 영역의 경로 계획 문제로 나눌 수도 있습니다. 이산 영역의 경로 계획 문제는 1차원 정적 최적화 문제로, 단순화된 환경 정보 이후의 경로 최적화 문제와 동일하며, 연속 영역의 경로 계획 문제는 연속적인 다차원 동적 환경의 문제입니다. . 경로 계획의 일반 단계 로봇, 항공기 등의 동적 경로 계획 문제와 같은 연속 영역의 경로 계획 문제의 일반적인 단계에는 주로 환경 모델링, 경로 검색 및 경로 평활화의 세 가지 링크가 포함됩니다. (1) 환경 모델링. 환경 모델링은 경로 계획에서 컴퓨터가 사용하기 편리한 환경 모델을 구축하는 것, 즉 실제 물리적 공간을 알고리즘으로 처리할 수 있는 추상 공간으로 추상화하는 것이 목적입니다. 상호 매핑을 달성합니다. (2) 경로 검색. 경로 탐색 단계는 환경 모델을 기반으로 해당 알고리즘을 적용하여 걷는 경로를 찾아 미리 정해진 성능 함수가 최적의 값을 얻을 수 있도록 하는 단계이다. (3) 길은 평탄하다. 해당 알고리즘을 통해 검색된 경로는 반드시 움직이는 신체가 걸을 수 있는 실행 가능한 경로는 아닙니다. 이를 실용적인 경로로 만들기 위해서는 추가 처리 및 평활화가 필요합니다. 개별 영역 내의 경로 계획 문제나 환경 모델링 또는 경로 검색 이전에 경로 타당성 분석이 수행된 문제의 경우 경로 평탄화 링크가 생략될 수 있습니다. 일반적으로 사용되는 알고리즘 경로 계획 방법에는 여러 가지가 있으며 각 방법의 장점과 단점에 따라 적용 범위가 달라집니다. 다양한 분야에서 일반적으로 사용되는 경로 계획 알고리즘에 대한 연구를 바탕으로 다양한 알고리즘의 발견 순서와 알고리즘의 기본 원리에 따라 알고리즘은 크게 전통적인 알고리즘, 그래픽 방법, 지능형 생체 공학 알고리즘 및 네 가지 범주로 구분됩니다. 다른 알고리즘. 기존 알고리즘 기존 경로 계획 알고리즘에는 시뮬레이션 어닐링 알고리즘, 인공 전위 필드 방법, 퍼지 논리 알고리즘, 금기 검색 알고리즘 등이 포함됩니다. (1) 시뮬레이션 어닐링(SA)은 대규모 조합 최적화 문제에 적합한 효과적인 근사 알고리즘입니다. 고체의 어닐링 과정을 모방하고 초기 온도, 초기 상태 및 냉각 속도를 설정하여 지속적인 온도 감소를 제어하고 확률적 점프 특성을 결합하며 솔루션 공간의 이웃 구조를 사용하여 무작위 검색을 수행합니다. 간단한 설명, 유연한 사용, 높은 작동 효율성, 초기 조건 제한이 거의 없다는 장점이 있지만 수렴 속도가 느리고 임의성이 적용 과정에서 중요한 링크라는 단점이 있습니다. (2) 인공 전위장법은 가상력법이다. 중력 반발력을 받는 물체의 움직임을 시뮬레이션합니다. 목표 지점과 움직이는 물체 사이에는 중력이 있고, 움직이는 물체와 장애물 사이에는 중력장과 척력장 기능을 설정하여 경로 최적화가 수행됩니다. 계획된 경로가 원활하고 안전하며 설명이 간단하다는 장점이 있지만, 알고리즘을 성공적으로 적용하려면 중력장의 설계가 중요합니다.

(3) 퍼지 논리 알고리즘 네트워크는 운전자의 운전 경험을 시뮬레이션하고 생리적 인식과 행동을 결합하며 시스템의 실시간 센서 정보를 기반으로 테이블 조회를 통해 계획 정보를 획득하여 경로 계획을 구현합니다. 알고리즘은 인간의 사고 습관을 따르고 수학적 모델링이 필요 없으며 전문 지식을 제어 신호로 쉽게 변환할 수 있습니다. 일관성, 안정성 및 연속성이 우수합니다. 그러나 퍼지 규칙을 요약하는 것이 어렵고 퍼지 규칙이 결정되면 온라인으로 조정하기 어렵고 적응성이 좋지 않습니다. 가장 큰 문제는 최적의 멤버십 기능, 통제 규칙 및 온라인 조정 방법입니다. (4) 타부 검색 알고리즘(TS)은 글로벌 단계별 최적화 알고리즘이자 인간 지능 과정을 시뮬레이션한 것입니다. 참여 검색을 피하기 위해 유연한 스토리지 구조와 해당 승격 규칙을 도입하고 기준을 무시하여 일부 긴급한 양호한 상태를 면제함으로써 글로벌 최적화를 달성합니다. 그래픽 방법 기존 알고리즘은 실제 문제를 해결할 때 모델링에 어려움을 겪는 경우가 많습니다. 그러나 그래픽 방법은 일반적으로 검색 기능이 부족하여 전문 검색 알고리즘과 결합해야 하는 경우가 많습니다. 그래픽 방법에는 C 공간 방법, 그리드 방법, 자유 공간 방법, 보로노이 다이어그램 방법 등이 포함됩니다. (1) C 공간 방식은 시각적 공간 방식이라고도 하는데, 이는 모션 공간에서 장애물을 다각형으로 확장하고 시작점과 끝점 및 모든 다각형 꼭지점 사이를 가능한 직선으로 연결하는 것입니다(*** 장애물을 통과하여 연결) 경로 범위에 대한 최단 경로를 검색합니다. C-space 방법의 장점은 직관적이고 최단 경로를 쉽게 찾을 수 있다는 점이며, 단점은 일단 시작점과 목표점이 변경되면 시각적 다이어그램을 재구성해야 하므로 유연성이 부족하다는 것입니다. 즉, 로컬 경로 계획 능력이 좋지 않아 전역 경로 계획 및 연속 영역 내 경로 계획에 적합합니다. 특히 전역 경로 계획의 환경 모델링에 적합합니다. (2) 여유 공간 방식은 시각적 그래프 방식의 적응성이 떨어지는 단점을 보완하기 위해 미리 정의된 기본 모양(예: 일반화된 원뿔, 볼록 다각형 등)을 사용하여 여유 공간을 구성하고, 여유 공간을 다음과 같이 표현합니다. 그래프를 연결한 다음 경로 계획을 위해 그래프를 검색합니다. 시작점과 끝점이 변경되면 구성된 여유 공간에서의 위치 변경과 동일하기 때문에 전체 그래프를 다시 그리지 않고 위치를 변경하기만 하면 됩니다. 단점은 장애물이 많으면 알고리즘의 복잡도가 높아져 알고리즘 구현이 어렵다는 점이다. (3) 그리드 방식, 즉 코드화된 그리드를 사용하여 지도를 표현하고, 장애물이 포함된 그리드를 장애물 그리드로 표시하거나 그 반대의 경우 자유 그리드로 표시하는 방식을 기준으로 경로 탐색을 수행합니다. 그리드 방식은 일반적으로 경로 계획을 위한 환경 모델링 기술로 사용되는데, 경로 계획 방법으로는 복잡한 환경 정보 문제를 해결하기 어렵고 일반적으로 다른 지능형 알고리즘과의 결합이 필요하다. (4) 보로노이 다이어그램은 공간적 근접 관계에 대한 기본적인 데이터 구조이다. 요소라고 불리는 몇 가지 기본 그래픽을 사용하여 공간을 나누고, 각 두 점 사이의 중간 수직선을 사용하여 요소의 측면을 결정하고, 마지막으로 전체 공간을 컴팩트한 보로노이 다이어그램으로 나눈 다음 알고리즘을 사용하여 측면을 결정합니다. 형성된 경로 네트워크는 최적의 검색에 사용됩니다. 장점은 장애물이 요소로 둘러싸여 있어 효과적으로 장애물을 피할 수 있다는 점입니다. 단점은 그래프를 다시 그리는 데 시간이 많이 걸리기 때문에 대규모 동적 환경에는 적합하지 않다는 것입니다. 지능형 생체공학 알고리즘 복잡한 동적 환경 정보 하에서 경로 계획 문제를 처리할 때 자연에서 얻은 영감이 매우 좋은 역할을 하는 경우가 많습니다. 지능형 생체공학 알고리즘은 생체공학 연구를 통해 발견된 알고리즘입니다. 일반적으로 사용되는 알고리즘에는 개미 군체 알고리즘, 신경망 알고리즘, 입자 떼 알고리즘, 유전자 알고리즘 등이 있습니다. (1) 개미 군집 알고리즘(ACA)의 아이디어는 개미 군집의 먹이 활동을 탐색하는 데서 유래합니다. 각 개미는 먹이를 찾아 이동하는 길에 일정 농도의 페로몬을 남깁니다. 동시에, 네트워크 내의 최단 경로에서는 개미의 통과 횟수가 많기 때문에 페로몬 농도가 높습니다. 또한 나중에 개미는 경로를 선택할 때 페로몬 농도를 기준으로 사용하게 됩니다. 따라서 긍정적인 피드백 효과를 통해 페로몬 농도가 높은 최단 경로가 매우 빠르게 발견됩니다. 알고리즘은 반복을 통해 개미 군집의 먹이 활동을 시뮬레이션하여 목표를 달성합니다. 우수한 전역 최적화 기능, 본질적인 병렬성 및 쉬운 컴퓨터 구현이라는 장점이 있지만 계산량이 많고 로컬 최적 솔루션에 빠지기 쉽습니다. 그러나 엘리트 개미 등을 추가하면 향상될 수 있습니다. 행동 양식. (2) 신경망 알고리즘은 인공지능 분야에서 매우 뛰어난 알고리즘으로 주로 동물 신경망의 행동을 시뮬레이션하고 분산병렬 정보처리를 수행한다. 그러나 경로 계획의 복잡하고 변화하는 환경은 수학 공식으로 설명하기 어렵기 때문에 경로 계획에 대한 적용은 성공적이지 못했습니다. 신경망을 사용하여 학습 표본 분포 공간 외부의 지점을 예측하는 경우 효과는 매우 클 것입니다. 차이점. 신경망은 학습 능력이 뛰어나지만 일반화 능력이 떨어지는 것이 치명적인 단점입니다. 그러나 강력한 학습 능력과 우수한 견고성으로 인해 다른 알고리즘과의 결합이 경로 계획 분야에서 화제가 되었습니다. (3) 유전 알고리즘(GA)은 현대 인공 지능 과학의 중요한 연구 분야로, 다윈의 유전 선택과 자연 제거의 생물학적 진화 과정을 시뮬레이션하는 계산 모델입니다. 그 아이디어는 생물학적 유전학과 적자생존의 자연 법칙에서 유래합니다. 유전학의 원리에 따라 구현된 반복 프로세스 검색 알고리즘입니다. 가장 큰 장점은 다른 알고리즘과 결합이 쉽고 반복의 장점을 최대한 발휘한다는 점이다. 단점은 계산 효율이 높지 않고 개미 집단 알고리즘만큼 좋지 않다는 점이다. 또한 현재 연구의 핫스팟이기도 합니다.

경로 계획 응용 경로 계획에는 로봇 매니퓰레이터 경로 계획, 항공기 궤적 계획, 순항 미사일 경로 계획, TSP(Traveling Salesman Problem) 및 이를 통해 파생된 다양한 차량(VRP) 경로 계획, 가상 조립 경로 등 광범위한 응용 분야가 있습니다. 계획, 도로망 기반 경로 계획, 전자지도 GPS 네비게이션 경로 검색 및 계획, 경로 문제 등 이산영역의 최단경로계획 문제 이산영역의 최단경로 계획에 속하는 문제로는 도로망 기반의 경로계획 문제, 전자지도 CPS 항로 탐색 및 계획 문제, 경로설정 문제 등이 있다. (1) 도로망과 전자지도를 기반으로 한 경로계획 GPS 내비게이션은 모두 GIS(지리정보시스템)를 기반으로 한 경로계획 문제로 볼 수 있다. 이러한 문제에 대한 해결책은 교차로를 노드로, 도로정보를 경로정보로 이용하여 복잡한 데이터정보에서 필요한 도로정보를 추출하는 것으로, 복합 경로정보 토폴로지 네트워크를 구축하고, 이 토폴로지에 출발점과 목표점을 위치시킨다. 네트워크의 두 노드는 경로 검색 알고리즘을 사용하여 최단 경로 최적화 계획을 수행합니다. (2) 라우팅 문제는 통신 기술 분야 연구의 초점입니다. 라우팅 문제의 주요 기능은 소스 노드에서 목적지 노드까지 데이터 정보를 원활하게 전달하는 것이다. Qos의 설계 요구 사항에 따라 경로에 다양한 가중치를 설정할 수 있으며 경로 매개 변수를 정의할 수 있습니다. 네트워크 토폴로지에서 최적의 경로를 안정적이고 효율적으로 검색하고 신속하게 집계합니다. 실시간 네트워크 혼잡 제어 및 특정 조건에 따른 동적 라우팅 선택. (3) 최단 경로 계획의 관점에서 볼 때 이러한 유형의 문제의 특징은 경로 정보(노드 수, 경로 매개변수 정보, 토폴로지 구조 등)가 알려진 시작 노드에서 대상 노드까지 모두 유사합니다. .) 최적 경로 계획 문제의 경우 경로 정보는 대부분 정적인 정보로 알려져 있으며, 정보에 변화가 있더라도 지능적인 알고리즘은 적시에 비상 계획을 수행할 수 있는 충분한 능력을 갖추고 있습니다. 일반적으로 사용되는 알고리즘에는 Dijkstra 알고리즘, A* 검색 알고리즘, 시뮬레이션 어닐링 알고리즘, 개미 식민지 알고리즘, 유전자 알고리즘, 입자 떼 알고리즘, Floyd 알고리즘, Fallback 알고리즘 등이 있습니다. 이산 영역의 에르고딕 최적 경로 문제 이산 영역의 에르고딕 최적 경로에 속하는 문제로는 가상 조립 경로 계획, 순회 판매원 문제(TSP) 및 다양한 차량 문제(VRP) 및 이들로부터 파생되는 물류 문제가 있습니다. 가상 조립 경로 계획의 핵심은 조립 순서 계획 문제이므로 순서 계획 문제는 전형적인 TSP 문제입니다. 이 유형의 문제의 일반적인 특징은 알려진 경로 정보가 정적 정보라는 것입니다. 자전거 문제의 경우 시작점이 고유하고 최종 대상 노드가 시작점이며 중간에 여러 하위 대상 노드가 있습니다. 차량은 최단 경로의 출발점에서 출발하여 모든 하위 대상 노드를 통과한 후 출발점으로 복귀해야 합니다. 물론, 어떤 문제는 가장 짧은 시간이나 가장 적은 비용을 계획 목표로 삼는다. 이러한 경로 계획 문제의 경우 해당 경로 정보를 경로 시간 정보나 경로 비용 정보로 조정할 수 있으며 해당 노드는 그대로 유지된다. 또한, 다수의 차량, 다수의 출발점, 부하 등의 요인에 대한 고려로 인한 전반적인 제어 문제도 있으며, 이러한 문제는 페달 차량의 경로 계획 문제의 연장선이다. 이러한 경로 문제를 해결하기 위해 일반적으로 사용되는 지능형 알고리즘에는 개미 식민지 알고리즘, 금기 검색 알고리즘, 시뮬레이션 어닐링 알고리즘, 신경망 알고리즘, 유전자 알고리즘, 입자 떼 알고리즘 등이 있습니다. 연속 영역 내 전역 경로 계획 문제 연속 영역 내 전역 경로 계획 다이어그램에 속하는 문제로는 로봇 매니퓰레이터 자율 이동 경로 계획, UAV 항공기 궤적 계획, 순항 미사일 궤적 계획 등이 있습니다. 이러한 유형의 문제는 경로 계획의 관점에서 볼 때, 환경 정보가 알려져 있고, 환경 정보가 정적인 정보일 때 어떻게 안전한 범위 내에서 장애물을 피하고 목적지까지의 최단 경로를 찾는 문제이다. 이러한 문제를 해결하려면 환경 모델링과 결합된 지능형 알고리즘이 필요한 경우가 많습니다. 이러한 문제에 직접 적용되는 경로 계획 알고리즘으로는 시각적 그래프 방법, 여유 공간 방법, 보로노이 다이어그램 방법, 그리드 방법, 페널티 함수 방법, 시뮬레이션 어닐링 알고리즘 등이 있습니다. 간접적으로 적용되는 지능형 알고리즘에는 A* 검색 알고리즘, 개미 군체 알고리즘, 유전자 알고리즘, 입자 떼 알고리즘, 인공 전위 필드 방법 등이 포함됩니다. 연속 도메인 내의 로컬 경로 계획 문제 연속 도메인 내의 로컬 경로 계획과 전역 경로 계획의 응용 분야는 기본적으로 동일하며 응용 분야 내에서 서로 다른 환경을 대상으로 하며 서로 다른 문제를 해결합니다. 지역 계획은 역동적이고 실시간 환경 정보를 다루며 온라인 계획에 속하며, 알고리즘은 우수한 실시간 성능, 높은 효율성 및 안정성을 요구하며 현재 연구 핫스팟입니다. 이러한 문제에 적용되는 경로 계획 알고리즘으로는 개미 군체 알고리즘, 유전 알고리즘, 입자 떼 알고리즘, A* 검색 알고리즘, 인공 전위장 방법, 양자 입자 떼 알고리즘, 신경망 알고리즘 등이 있습니다. 연속 영역 내의 에르고딕 경로 계획 문제 연속 영역 내의 에르고딕 경로 계획은 주로 청소 로봇, 잔디 다듬기, 지뢰 제거 로봇, 수색 및 구조 로봇, 광물 탐지기 등에 적용됩니다. 그 특징은 다음과 같습니다. 로봇은 작업 영역의 모든 구석구석을 커버하기 위해 최단 경로를 사용해야 하므로 최대 범위와 최소 반복률이 필요합니다. 이러한 문제를 해결하기 위해서는 먼저 환경 모델링이 이루어져야 하며, 가장 일반적으로 사용되는 방법은 그리드(Grid) 방법이며, 이후 노이만 드 카르발류(Neumann de Carvalho R) 등이 템플릿 모델 방법을 개발했습니다. 이러한 문제를 해결하기 위해 일반적으로 사용되는 알고리즘에는 신경망 알고리즘, A* 알고리즘, 유전자 알고리즘, 입자 떼 알고리즘, 개미 식민지 알고리즘 등이 있습니다.

경로계획의 미래 발전 과학기술이 지속적으로 발전함에 따라 경로계획 기술이 적용되는 환경은 더욱 복잡하고 변화무쌍해질 것이다. 이를 위해서는 복잡한 환경 변화에 신속하게 대응할 수 있는 경로 계획 알고리즘이 필요합니다. 이는 현재 단일 또는 일방적 알고리즘으로 해결할 수 있는 문제가 아닙니다. 따라서 향후 경로 계획 기술에서는 새로운 경로 계획 알고리즘의 연구 및 발굴 외에도 다음과 같은 측면에 주목해야 합니다. ) 고급 경로 계획 알고리즘 개선. 모든 알고리즘은 실제 적용 과정에서 많은 어려움, 특히 자체적인 한계에 직면하게 됩니다. 예를 들어, A* 알고리즘은 휴리스틱 검색 알고리즘으로 견고성과 빠른 응답이라는 특징을 가지고 있지만 실제로 적용할 때 여전히 단점이 있습니다. UAV 궤도 계획에 적용할 때 A* 알고리즘의 단점에 대해 Li Ji는 말했습니다. 에서는 A* 알고리즘이 직접 비행 제한을 충족하기 어렵고 항공기의 최소 회전 반경 등의 제한이 있었던 문제를 해결한 향상된 A* 알고리즘을 제안했습니다. (2) 경로 계획 알고리즘(즉, 하이브리드 알고리즘)의 효과적인 조합. 실제 응용에서 단일 경로 계획 알고리즘이 모든 경로 계획 문제를 해결하는 것은 불가능합니다. 특히 새로운 학제간 문제의 경우 경로 계획 알고리즘의 보완적인 장점으로 이 문제를 해결할 수 있습니다. 가능성이 제공됩니다. 다중 우주 정거장 경로 계획 문제에 대해 Jin Feihu 등은 개미 군집 알고리즘과 신경망 방법을 결합하여 이 문제를 해결하고 단순히 신경망 알고리즘을 사용할 때 발생하는 로컬 최소 문제를 피했습니다. (3) 환경 모델링 기술과 경로 계획 알고리즘의 결합. 복잡한 2차원 또는 심지어 3차원의 연속적인 동적 환경 정보를 처리할 때 알고리즘이 할 수 있는 작업은 제한적입니다. 좋은 모델링 기술과 우수한 경로 계획 알고리즘의 결합은 이 문제를 해결하는 방법이 될 것입니다. 그리드 방식과 개미 군집 알고리즘의 조합, C 공간 방식과 다익스트라 알고리즘의 조합 등 (4) 다중 지능형 신체 병렬 경로 계획 알고리즘 설계. 과학기술의 응용개발로 다중지능체의 병렬협력이 적용되고 있다. 그 중에서 다중 로봇 협업과 이중 조작기 협업에서 경로 충돌 문제는 점점 더 많은 관심을 끌고 있습니다. 충돌 없는 경로 계획을 달성하는 방법은 향후 연구에서 뜨거운 주제 중 하나가 될 것입니다.