Using machine learning with random sample-based methods for faster path planning and optimization = 빠른 경로 계획 및 최적화를 위한 무작위 표본 추출 방법에서의 기계 학습 활용

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 54
  • Download : 0
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.
Kim, Jong-Hwanresearcher김종환researcher
한국과학기술원 :전기및전자공학부,
Issue Date

학위논문(석사) - 한국과학기술원 : 전기및전자공학부, 2018.2,[vii, 60 p. :]


Random Sample-Based▼aPath-Planning▼aLocal Optimization▼aBatch Informed Trees▼aBias Samples▼aShort-Cutting; 랜덤 샘플 기반▼a경로 계획▼a로컬 최적화▼a일괄 처리 된 트리▼a바이어스 샘플▼a숏컷▼a지역 최적화▼a기계 학습

Appears in Collection
Files in This Item
There are no files associated with this item.


  • mendeley


rss_1.0 rss_2.0 atom_1.0