Optimal Spline-based RRT Path Planning Using Probabilistic Map

Kwangjin Yang,Seng Keat Gan,Jinwook Huh,Sanghyun Joo 제어로봇시스템학회 2014 제어로봇시스템학회 국제학술대회 논문집 Vol.2014 No.10

This paper presents an optimal path planning algorithm that adopts the rapidly-exploring random tree(RRT) as a path planner. The RRT generates a valid path quickly, but it does not have the ability to control the quality of the path. In this paper, the nonholonomic path planning and the optimal path planning are tackled simultaneously within the RRT framework. The spline-based RRT algorithm generates a feasible path satisfying the differential constraints, and the RRT? strategy is incorporated to guarantee the optimal solution. In addition, the probabilistic map combining 3D Lidar and visual camera is used as a map for the path planning. Simulation results show that the proposed spline-based RRT? outputs a dynamically feasible optimal path.

인간주관적 요소(Human Factors)를 고려한 대규모 복합건물내 보행자 최적경로탐색 시스템 개발

윤상원(Yoon Sangwon),배상훈(Bae Sanghoon) 대한토목학회 2007 대한토목학회논문집 D Vol.27 No.5D

미래 사회로 갈수록 건물이 점차 대형화 복잡화됨에 따라 건물 내에서 이용자들에게 혼란을 주지 않고 목적지까지 효율적으로 도착하게 하는 안내시스템의 필요성이 제기되고 있다. 대규모 복합도로에 관련하여서는 많은 최적경로 산정 모형들이 제시되고 있는 반면, 건물 내에서 보행자의 이동에 관한 최적경로에 대한 연구는 미비하다. 따라서 본 연구는 미래형 복합건물 내에서 승용차를 이용하는 사용자가 주차장에서 건물 내의 목적지까지 이동하는 최적의 경로를 제시할 수 있는 최적경로 탐색모형을 제시하였다. 모형에 쓰이는 알고리즘에 거리, 이동시간과 같은 객관적인 요소뿐 아니라 피로감, 쾌적도, 대기시간을 고려한 선호도 등의 인간의 주관적 요소도 적용함으로써 보다 미래지향성을 부가하였다. 다익스트라(Dijkstra) 알고리즘을 통하여 거리의 최소비용을 산정하였고, 주관적 요소를 반영하기 위하여 순위합, 산술합 방법을 사용하여 객관성을 부가하였다. 마지막으로 가상 시나리오를 통한 알고리즘의 효율성과 독창성을 검증하였다. 검증결과 개발모형을 통했을 경우 그렇지 않을 경우보다, 수직이동 경로차이의 시나리오에서 약 75%, 수평이동 경로차이의 시나리오에서 약 24.5~107.7% 더 효율적으로 나타났다. As a trend that the size of building is getting larger and more complex, it is essential to introduce guidance system to users to mitigate their confusion. There were several studies for choosing optimal path for the road, but not sufficient studies were conducted for that of the building. Therefore, this study is to develop the system for selecting optimal path from the parking lot to useris destination at certain layer in the building. Not only objective factors such as distance and required time for method of movement, but subjective factors such as fatigue, freshness and preference are considered to decide the optimal path. To define the minimum cost of moving distance, Dijkstra algorithm and evaluation function which is considered human factor are used in this study. Lastly, some scenarios demonstrate the characteristic and originality of selecting optimal path algorithm in this study.

유전자 알고리즘을 이용한 최적침투경로 분석

방수남,손홍규,김상필,김창재,허준,Bang, Soo-Nam,Sohn, Hyong-Gyoo,Kim, Sang-Pil,Kim, Chang-Jae,Heo, Joon 대한원격탐사학회 2011 大韓遠隔探査學會誌 Vol.27 No.1

최적침투경로 분석은 GIS 기술을 군사적 목적을 위해 유용하게 사용할 수 있는 대표적인 분야 중 하나이다. 그러나 군사목적의 최적경로분석은 일반적인 최적경로분석이 네트워크 데이터에서 이루어지는 것과는 달리 래스터 데이터에서 이루어져야한 필요가 있으며, 래스터 데이터에서의 연산량은 네트워크 데이터를 사용할 때에 비해 급격히 증가하기에, 연산량은 많으나 일반적으로 네트워크 데이터에서 최적경로 탐색을 위해 사용되는 Dijkstra 알고리즘과 같은 방법을 적용시키기 어렵게 만든다. 따라서, 본 연구에는 최적화문제에서 우수한 성과를 거둔 유전자 알고리즘(Genetic algorithm)을 최적경로분석에 적용시켜 문제를 해결하고자 하였다. 이를 위해 최적침투경로를 적의 탐지에 발각될 확률을 최소화 시킬 수 있는 경로로 결정하고, 래스터 데이터에서의 침투경로분석에 적합한 2차원 2진 배열 (2D binary array)형태의 유전자형 및 이들의 교차(crossover) 및 변이(mutation) 방법을 제안하였다. 제안된 방법에 대한 실험은 개체집단의 크기를 500, 1000, 2000, 3000으로 증가시켜가며 각각의 경우에 대해 30번씩 실험을 수행하였다. 실험결과 세대가 거듭될수록 평균 누적탐지확률이 안정적으로 감소하며 성공적으로 최적침투경로를 찾아 수렴하였으며, 개체집단의 크기가 커질수록 그 성능이 향상되는 것을 확인할 수 있었다. The analysis of optimal infiltration path is one of the representative fields in which the GIS technology can be useful for the military purpose. Usually the analysis of the optimal path is done with network data. However, for military purpose, it often needs to be done with raster data. Because raster data needs far more computation than network data, it is difficult to apply the methods usually used in network data, such as Dijkstra algorithm. The genetic algorithm, which has shown great outcomes in optimization problems, was applied. It was used to minimize the detection probability of infiltration route. 2D binary array genes and its crossover and mutation were suggested to solve this problem with raster data. 30 tests were performed for each population size, 500, 1000, 2000, and 3000. With each generation, more adoptable routes survived and made their children routes. Results indicate that as the generations increased, average detection probability decreased and the routes converged to the optimal path. Also, as the population size increases, more optimal routes were found. The suggested genetic algorithm successfully finds the optimal infiltration route, and it shows better performance with larger population.

Studies on optimal control approach in a fed-batch fermentation

Amornchai Arpornwichanop,Natthapong Shomchoam 한국화학공학회 2007 Korean Journal of Chemical Engineering Vol.24 No.1

operation of fermentation processes has been receiving a great deal of interest as it offers thepossibility to control a substrate concentration at a desired condition. However, control of a fed-batch fermentationreactor has been known to be a difficult task due to its highly nonlinear and complicated behavior. This work addressesan optimization-based control strategy for a fed-batch bioreactor where an ethanol fermentation process is chosen asa case study. The optimal control problem is formulated to determine the optimal feeding rate policy giving the highestproduct yield. The resulting optimization problem is solved by using an efficient sequential approach with a piecewiseconstant control parameterization. Due to the limitation of the sequential approach to cope with inequality path con-time interval and switching time on the solution of the optimal control is investigated.

유전자 알고리즘을 이용한 최적침투경로 분석

방수남 ( Soo Nam Bang ),손홍규 ( Hyong Gyoo Sohn ),김상필 ( Sang Pil Kim ),김창재 ( Chang Jae Kim ),허준 ( Joon Heo ) 대한원격탐사학회 2011 大韓遠隔探査學會誌 Vol.27 No.1

최적침투경로 분석은 GIS 기술을 군사적 목적을 위해 유용하게 사용할 수 있는 대표적인 분야 중 하나이다. 그러나 군사목적의 최적경로분석은 일반적인 최적경로분석이 네트워크 데이터에서 이루어지는 것과는 달리 래스터 데이터에서 이루어져야할 필요가 있으며, 래스터 데이터에서의 연산량은 네트워크 데이터를 사용할 때에 비해 급격히 증가하기에, 연산량은 많으나 일반적으로 네트워크 데이터에서 최적경로 탐색을 위해 사용되는 Dijkstra 알고리즘과 같은 방법을 적용시키기 어렵게 만든다. 따라서, 본 연구에는 최적화문제에서 우수한 성과를 거둔 유전자 알고리즘(Genetic algorithm)을 최적경로분석에 적용시켜 문제를 해결하고자 하였다. 이를 위해 최적침투경로를 적의 탐지에 발각될 확률을 최소화 시킬 수 있는 경로로 결정하고, 래스터 데이터에서의 침투경로분석에 적합한 2차원 2진 배열(2D binary array)형태의 유전자형 및 이들의 교차(crossover) 및 변이(mutation) 방법을 제안하였다. 제안된 방법에 대한 실험은 개체집단의 크기를 500, 1000, 2000, 3000으로 증가시켜가며 각각의 경우에 대해 30번씩 실험을 수행하였다. 실험결 The analysis of optimal infiltration path is one of the representative fields in which the GIS technology can be useful for the military purpose. Usually the analysis of the optimal path is done with network data. However, for military purpose, it often needs to be done with raster data. Because raster data needs far more computation than network data, it is difficult to apply the methods usually used in network data, such as Dijkstra algorithm. The genetic algorithm, which has shown great outcomes in optimization problems, was applied. It was used to minimize the detection probability of infiltration route. 2D binary array genes and its crossover and mutation were suggested to solve this problem with raster data. 30 tests were performed for each population size, 500, 1000, 2000, and 3000. With each generation, more adoptable routes survived and made their children routes. Results indicate that as the generations increased, average detection probability decreased and the routes converged to the optimal path. Also, as the population size increases, more optimal routes were found. The suggested genetic algorithm successfully finds the optimal infiltration route, and it shows better performance with larger population.

과수원 작업기의 작업 경로 최적화를 위한 오더 피킹 알고리즘

황규영,조성인,박두산 한국농업기계학회 2008 바이오시스템공학 Vol.33 No.1

The purpose of this study is to develop an optimal path planning program for autonomous speed sprayer in orchard. A digital map which contains coordinate information and entity information including height, width, radius of main stem, and disease of a trees was developed to build an optimal path. The digital map, dynamic programming and order-picking algorithm have used for planning an optimal path for autonomous speed sprayer. When this algorithm applied to rectangular-shaped orchards to travel whole trees in the orchard, the developed program planned the same working path and same traveling distance as those of created by conventional method. But to irregular-shaped orchards, developed program planned different and 5.06% shorter path than conventional method. When applied to create path for multi-selected trees, irregular-shaped orchards showed 13.9% shorter path and also rectangular-shaped orchards showed 9.1% shorter path. The developed program always planned shorter path than the path created by conventional method despite of variation of shape of orchards.

Path Planning Algorithm Using the Particle Swarm Optimization and the Improved Dijkstra Algorithm

Hwanil Kang,Byunghee Lee,Wooseok Jang 한국지능시스템학회 2007 한국지능시스템학회 학술발표 논문집 Vol.17 No.2

In this paper, we develop the path planning algorithm using the improved Dijkstra algorithm and the particle swarm optimization. To get the optimal path, at first we construct the MAKLINK on the world environment and then make a graph associated with the MAKLINK. From the graph, we obtain the Dijkstra path between the starting point and the destination point. From the optimal path, we search the improved Dijkstra path using the graph. Finally, applying the particle swarm optimization to the improved Dijkstra path, we obtain the optimal path for the mobile robot. It turns out that the proposed method has better performance than the result in [1].

Heterogeneous-ants-based Path Planner for Global Path Planning of Mobile Robot Applications

이준우 제어·로봇·시스템학회 2017 International Journal of Control, Automation, and Vol.15 No.4

Mobile robots can be applied to a wide range of problems, and the demand for these applications hasrisen in recent years, increasing interest in the study of mobile robotics. Many studies have examined the pathplanning problem, one of the most important issues in mobile robotics. However, the grid paths found by traditionalplanners are often not the true shortest paths or are not smooth because their potential headings are artificiallyconstrained to multiples of 45 degrees. These paths are unfit for application to mobile robots because the highnumber of heading changes increases the energy required to move the mobile robot. Some studies have proposed apost-processing step to smooth the grid path. However, in this case, the post-smoothed path may not necessarily findthe true shortest path because the post-smoothed path is still constrained to headings of multiples of 45 degrees. Thisstudy attempts to develop a global path planner that can directly find an optimal and smoother path without postprocessingto smooth the path. We propose a heterogeneous-ants-based path planner (HAB-PP) as a global pathplanner to overcome the shortcomings mentioned above. The HAB-PP was created by modifying and optimizingthe global path planning procedure from the ant colony optimization (ACO) algorithm. The proposed algorithmdiffers from the traditional ACO path planning algorithm in three respects: modified transition probability functionfor moving ants, modified pheromone update rule, and heterogeneous ants. The simulation results demonstrate theeffectiveness of the HAB-PP.

Mechanism optimal design of backhoe hydraulic excavator working device based on digging paths

Jin Chen,Fei Qing,Xiaoping Pang 대한기계학회 2014 JOURNAL OF MECHANICAL SCIENCE AND TECHNOLOGY Vol.28 No.1

In order to solve the problem that hydraulic excavator in the real working process cannot meet the design requirements and reveals insufficientdigging force, a new method on mechanism optimal design of backhoe hydraulic excavator working device based on diggingpaths is introduced and discussed in this paper. Considering the characteristics of consecutive digging process of hydraulic excavator, adigging path is composed of bucket digging trajectories and arm digging trajectories. The feasible working region is divided into a seriesof uniform paths according to the working position of boom. The practical digging performance of excavator is evaluated based on thedigging force parameters under combined work condition of the discrete points on the digging paths. It is turned out that the method ismore accurate to analyze excavator's real-world digging performance via the analysis of some practical cases. Based on the new diggingperformance analysis method, the optimization mathematical model is built to ensure the digging force under combined work conditionand the average digging force of every operating path as big as possible. The layout design of hinge position on the working device isoptimized through genetic algorithm. The optimization result shows that a certain model of an excavator's maximum digging force on thecustomary digging paths is improved by 10% and the average digging force is improved by 4% after the optimization on the workingdevice of the excavator with weak digging force.

무인 자율 주행을 위한 최단 시간 경로계획 알고리즘 설계

김동욱(Dongwook Kim),김학구(Hakgu Kim),이경수(Kyongsu Yi) 대한기계학회 2013 大韓機械學會論文集A Vol.37 No.5

본 논문은 무인 자율 주행을 위한 최소 시간 경로계획 알고리즘에 대해서 제안하였다. 최소 시간 경로계획 문제는 경로의 기하학적인 형상에 대한 고려뿐만이 아니라 차량 동역학까지 고려해야 하는 최적 문제이다. 경로계획은 후보 경로 생성 알고리즘과 속도 최적화 알고리즘으로 구성된다. 후보 경로 생성 알고리즘은 최단 거리 경로와 최고 속도 경로를 조합하여 후보경로를 생성한다. 속도 최적화 알고리즘은 차량의 주행성능 한계와 타이어 마찰 한계를 고려하여 각 후보 경로의 최고 속도를 계산한다. 이렇게 계산된 경로와 속도를 이용하여 각 후보 경로의 주행 시간을 계산하고 가장 작은 주행 시간의 경로를 최단시간 경로로 도출한다. 그리고 제안한 알고리즘은 CarSim 과 Matlab/Simulink 를 사용한 시뮬레이션을 통해 검증하였다. This paper presents a near-minimum time path planning algorithm for autonomous driving. The problem of near-minimum time path planning is an optimization problem in which it is necessary to take into account not only the geometry of the circuit but also the dynamics of the vehicle. The path planning algorithm consists of a candidate path generation and a velocity optimization algorithm. The candidate path generation algorithm calculates the compromises between the shortest path and the path that allows the highest speeds to be achieved. The velocity optimization algorithm calculates the lap time of each candidate considering the vehicle driving performance and tire friction limit. By using the calculated path and velocity of each candidate, we calculate the lap times and search for a near-minimum time path. The proposed algorithm was evaluated via computer simulation using CarSim and Matlab/Simulink.