This paper presents a framework for improving path planning and optimization via combination of techniques in machine learning, and random-sample optimization methods. This includes both modifying previous state-of-the-art methods in random-sample based planners, and additionally using machine learning to optimize their growth. Generally random sample-based planners have three stages in planning: Initial Planning, Global Optimization, and Path Simplification (Local Optimization). This disseration primarily focuses on improving the speed of initial path planning and path simplification to allow for fast, local optimal and realistic paths to be created, with the implication that the need to the exact optimal homotopic path class is less important in most cases of real-world robotics.
Firstly we present $Fast-BIT^*$ which modifies the underlying heuristic that dictates the expansion and processing of vertex and edge queues. $BIT^*$ uses heuristics to guide the search of implicit Random Geometric Graphs (RGGs) to generate an explicit solution, while minimizing highly computational tasks such as collision checking. $Fast-BIT^*$ builds on $BIT^*$ by biasing the search heuristic towards the goal, in a solution analogous to depth-first search, finding an initial solution of the implicit RGG at a faster rate, at the cost of decreasing initial optimality. $Fast-BIT^*$ requires additional procedures to reset expansion variables of affected areas in the graph, ensuring the bias is not lasting in the graph expansion. An earlier initial solution leads to a faster initial upper bound for use in informed graph pruning, allowing convergence of path cost to begin earlier in the planning procedure. We show that $Fast-BIT^*$ finds a first solution faster than $BIT^*$ as well as the commonly used RRT-Connect and similar methods, along with a faster overall convergence rate. This dissertation shows various random-world test examples, showing the benefits of similar algorithms, along with a robot path planning simulation.
Secondly, a modification of the traditional Short-Cut called Reoriented Short-Cut ($RSC^*$) is presented, allowing \textit{almost sure}, single homotopy class, asymptotic convergence in high degree of freedom (DoF) problems. An additional Informed Gaussian Sampling ($IGS^*$) technique is also presented for convergence comparison. Short-Cut methods are used as a final technique to further optimize an initially found path. Typical short-cut methods fail due to the fact that a single DoF may converge faster than the remainder, creating a zero volume region to converge, halting further improvements. Previous attempts to fix this separate individual DoFs, resulting in drastic increases in collision checking computation. RSC and IGS shift the vertex to be Short-Cut to a different position, reorienting the line segments and removing the zero-volume convergence region. RSC uses rotates the chosen vertex around a plane orthogonal to the vector connect the two adjacent vertices; this creates a controllable translation of the vertex to a location that has a high probability of improvement. These methods are compared to similar strategies across a variety of sample problems including random worlds, and robot manipulation, to show the convergence across both translation and rotation oriented problems.
Recent research often attempts to apply machine learning approaches to solve classical problems in robotics; successfully resulting in algorithms capable of navigating an environment with high success. One major problem with machine learning such as in deep reinforcement learning control problems is reliability in avoiding collisions as complexity or unforeseen circumstances appear. Batch Intelligently-Informed Trees ($BI^2T^*$) employ machine learning in the form of Convolutional Auto-Encoders to learn the ideal sample distribution for random sample-based planner environments. This allows difficult to sample environments to be more easily traversed with knowledge from similarly learned experiences. Two-dimensional environments with point-to-point and rotational objects in 3 and 4 DoFs are tested to show the effectiveness of the solution.
이 백서에서는 기계 학습에서의 기법 조합과 무작위 표본 최적화 방법을 통한 경로 계획 및 최적화를 개선하기위한 프레임 워크를 제시합니다. 여기에는 무작위 표본 기반 계획자의 이전 최첨단 방법을 수정하는 것 외에도 기계 학습을 사용하여 성장을 최적화하는 것이 포함됩니다. 일반적으로 무작위 표본 기반 계획자는 초기 계획, 전역 최적화 및 경로 단순화 (로컬 최적화)의 세 단계로 구성됩니다. 이 논의는 주로 초기 경로 계획 및 경로 단순화의 속도 향상에 중점을 두어 실제 세계의 대부분의 사례에서 정확한 최적 동위 원소 경로 클래스에 대한 필요성이 덜 중요하다는 의미에서 신속하고 지역 최적의 현실적인 경로를 만들 수 있도록합니다 로봇 공학.
우선 우리는 버텍스 및 에지 큐의 확장 및 처리를 지시하는 기본 휴리스틱을 수정하는 $Fast-BIT^*$를 제시합니다. $BIT^*$는 암시 적 Random Geometry Graph (RGG) 검색을 통해 지능적 솔루션을 생성하고 추돌 검사와 같은 고도의 계산 작업을 최소화하는 추론을 사용합니다. $Fast-BIT^*$는 깊이 우선 검색과 유사한 솔루션에서 목표에 대한 검색 경험칙을 바이어 싱하여 $BIT^*$를 기반으로 초기 최적 성을 줄이거 나 더 빠른 속도로 암시 적 RGG의 초기 솔루션을 찾습니다. $Fast-BIT^*$는 그래프의 영향을받는 영역의 확장 변수를 재설정하는 추가 절차가 필요하므로 그래프 확장에서 바이어스가 지속되지 않도록합니다. 초기 초기 솔루션을 사용하면 정보 그래프의 프 루닝 (pruning)에 사용할 초기 상한이보다 빨라 지므로 계획 절차 초기에 경로 비용의 수렴이 가능합니다. $Fast-BIT^*$는 일반적으로 사용되는 RRT-Connect 및 유사한 방법뿐만 아니라 더 빠른 전체 수렴 속도와 함께 $BIT^*$보다 빠른 첫 번째 솔루션을 찾습니다. 이 논문은 로봇 경로 계획 시뮬레이션과 함께 유사한 알고리즘의 이점을 보여주는 다양한 임의의 세계 테스트 예제를 보여줍니다.
두 번째로, 전통적인 단축 컷 (Reoriented Short-Cut) ($RSC^*$)을 수정하여 높은 자유 도로 (DoF) 문제에서 점근 적으로 수렴하는 단일 호모티어 클래스를 허용합니다. 컨버전스 비교를 위해 $IGS^*$ (Informed Gaussian Sampling) 기술을 추가로 제시합니다. Short-Cut 방법은 초기에 발견 된 경로를 최적화하기위한 최종 기법으로 사용됩니다. 하나의 DoF가 나머지보다 빠르게 수렴 될 수있어 수렴 할 수있는 제로 볼륨 영역이 만들어지기 때문에 일반적인 지름길 방법은 실패합니다. 이전에는 개별적인 DoF를 개별적으로 수정하려고 시도했기 때문에 충돌 검사 계산이 크게 증가했습니다. RSC와 IGS는 정점을 Short-Cut으로 다른 위치로 이동하고 선 세그먼트의 방향을 바꾸고 제로 볼륨 컨버전스 영역을 제거합니다. RSC는 벡터에 직각 인 평면 주위에서 선택된 정점을 회전시켜 인접한 두 정점을 연결합니다. 이는 개선 가능성이 높은 위치로 정점의 제어 가능한 변환을 생성합니다. 이 방법은 무작위적인 세계와 로봇 조작을 포함한 다양한 표본 문제에 대한 유사한 전략과 비교되어 번역 및 회전 지향 문제 모두에서 수렴을 나타냅니다.
최근의 연구는 로봇 공학의 고전적 문제를 해결하기 위해 기계 학습 접근법을 적용하려고 시도합니다. 높은 성공률로 환경을 탐색 할 수있는 알고리즘을 성공적으로 만들어 냈습니다. 심층적 인 학습 제어 문제와 같은 기계 학습의 주요 문제점 중 하나는 복잡성이나 예기치 않은 상황이 나타나면 충돌을 회피하는 데있어서의 신뢰성입니다. Batch Intelligent-Informed Trees ($BI^2T^*$)는 Convolutional Auto-Encoders의 형태로 기계 학습을 사용하여 무작위 샘플 기반 플래너 환경에 이상적인 샘플 배포를 학습합니다. 따라서 유사한 환경에서 얻은 지식을 바탕으로 샘플 환경을 쉽게 탐색 할 수 있습니다. 3/4 DoF의 지점 간 및 회전 객체가있는 2 차원 환경을 테스트하여 솔루션의 효율성을 보여줍니다.
