G² Continuity Smooth Path Planning using Cubic Polynomial Interpolation with Membership Function

장성용,허욱열 대한전기학회 2015 Journal of Electrical Engineering & Technology Vol.10 No.2

Path planning algorithms are used to allow mobile robots to avoid obstacles and find ways from a start point to a target point. The general path planning algorithm focused on constructing of collision free path. However, a high continuous path can make smooth and efficiently movements. To improve the continuity of the path, the searched waypoints are connected by the proposed polynomial interpolation. The existing polynomial interpolation methods connect two points. In this paper, point groups are created with three points. The point groups have each polynomial. Polynomials are made by matching the differential values and simple matrix calculation. Membership functions are used to distribute the weight of each polynomial at overlapped sections. As a result, the path has continuity. In addition, the proposed method can analyze path numerically to obtain curvature and heading angle. Moreover, it does not require complex calculation and databases to save the created path.

G² Continuity Smooth Path Planning using Cubic Polynomial Interpolation with Membership Function

Chang, Seong-Ryong,Huh, Uk-Youl The Korean Institute of Electrical Engineers 2015 Journal of Electrical Engineering & Technology Vol.10 No.2

Path planning algorithms are used to allow mobile robots to avoid obstacles and find ways from a start point to a target point. The general path planning algorithm focused on constructing of collision free path. However, a high continuous path can make smooth and efficiently movements. To improve the continuity of the path, the searched waypoints are connected by the proposed polynomial interpolation. The existing polynomial interpolation methods connect two points. In this paper, point groups are created with three points. The point groups have each polynomial. Polynomials are made by matching the differential values and simple matrix calculation. Membership functions are used to distribute the weight of each polynomial at overlapped sections. As a result, the path has $G^2$ continuity. In addition, the proposed method can analyze path numerically to obtain curvature and heading angle. Moreover, it does not require complex calculation and databases to save the created path.

G<SUP>2</SUP> Continuity Smooth Path Planning using Cubic Polynomial Interpolation with Membership Function

Seong-Ryong Chang,Uk-Youl Huh 대한전기학회 2015 Journal of Electrical Engineering & Technology Vol.10 No.2

Path planning algorithms are used to allow mobile robots to avoid obstacles and find ways from a start point to a target point. The general path planning algorithm focused on constructing of collision free path. However, a high continuous path can make smooth and efficiently movements. To improve the continuity of the path, the searched waypoints are connected by the proposed polynomial interpolation. The existing polynomial interpolation methods connect two points. In this paper, point groups are created with three points. The point groups have each polynomial. Polynomials are made by matching the differential values and simple matrix calculation. Membership functions are used to distribute the weight of each polynomial at overlapped sections. As a result, the path has G<SUP>2</SUP> continuity. In addition, the proposed method can analyze path numerically to obtain curvature and heading angle. Moreover, it does not require complex calculation and databases to save the created path.

퍼지 이진화와 허프 변환을 이용한 주행 경로 검출

우영운(Young Woon Woo) 한국컴퓨터정보학회 2014 韓國컴퓨터情報學會論文誌 Vol.19 No.2

기존의 허프 변환을 이용한 차량 주행 경로 검출 기법에서는 배경 영상이 복잡하지 않은 차량 주행 영상에서 주행선 이탈 여부를 판별하였다. 하지만 획득된 차량 주행 영상에는 도로의 장애물이나 그림자, 다른 차량 등 주행 경로 인식을 방해하는 요소들이 있으므로 주행 경로 검출에 있어서 매우 큰 장애물로 작용하였다. 이 논문에서는 퍼지 이진화 기법과 캐니 마스크를 적용함으로써 기존에 제안된 허프 변환만을 이용한 주행 경로 검출 기법보다 효과적인 주행 경로 검출 기법을 제안한다. 이 논문에서 제안한 주행 경로 검출 기법의 성능을 평가하기 위하여 20개의 영상을 대상으로 실험한 결과, 주행 경로를 검출하는 데에 더욱 효과적인 것을 확인하였다. In conventional methods for car navigational path detection using Hough transform, navigational path deviation of a car is decided in car navigational images with simple background. But in case of car navigational images having complex background with obstacles on the road, shadows, other cars, and so on, it is very difficult to detect navigational path because these obstacles obstruct correct detection of car navigational path. In this paper, I proposed an effective navigational path detection method having better performance than conventional navigational path detection methods using Hough transform only, and fuzzy binarization method and Canny mask are applied in the proposed method for the better performance. In order to evaluate the performance of the proposed method, I experimented with 20 car navigational images and verified the proposed method is more effective for detection of navigational path.

선호도 기반 최단경로 탐색을 위한 휴리스틱 융합 알고리즘

옥승호(Seung-Ho Ok),안진호(Jin-Ho Ahn),강성호(Sungho Kang),문병인(Byungin Moon) 大韓電子工學會 2010 電子工學會論文誌-TC (Telecommunications) Vol.47 No.8

본 논문에서는 개미 군집 최적화 (Ant Colony Optimization; ACO) 및 A* 휴리스틱 알고리즘이 융합된 선호도 기반 경로탐색 알고리즘을 제안한다. 최근 ITS (Intelligent Transportation Systems)의 개발과 함께 차량용 내비게이션의 사용이 증가하면서 경로탐색 알고리즘의 중요성이 더욱 높아지고 있다. 기존의 Dijkstra 및 A*와 같은 대부분의 최단경로 탐색 알고리즘은 최단거리 또는 최단시간 경로 탐색을 목표로 한다. 하지만 이러한 경로 탐색 결과는 더 안전하고 특정 경로를 선호하는 운전자를 위한 최적의 경로가 아니다. 따라서 본 논문에서는 선호도 기반 최단 경로 탐색 알고리즘을 제안한다. 제안된 알고리즘은 주어진 맵의 링크 속성 정보를 이용하며, 각 링크에 대한 사용자 선호도는 내비게이션 사용자에 의해 설정되어 진다. 제안된 알고리즘은 C로 구현하였으며, 64노드 및 118링크로 구성된 맵에서 다양한 파라미터를 통해 성능을 측정한 결과 본 논문에서 제안한 휴리스틱 융합 알고리즘은 선호도 기반 경로뿐만 아니라 최단 경로 탐색에도 적합함을 알 수 있었다. In this paper, we propose a preference-based shortest path algorithm which is combined with Ant Colony Optimization (ACO) and A* heuristic algorithm. In recent years, with the development of ITS (Intelligent Transportation Systems), there has been a resurgence of interest in a shortest path search algorithm for use in car navigation systems. Most of the shortest path search algorithms such as Dijkstra and A* aim at finding the distance or time shortest paths. However, the shortest path is not always an optimum path for the drivers who prefer choosing a less short, but more reliable or flexible path. For this reason, we propose a preference-based shortest path search algorithm which uses the properties of the links of the map. The preferences of the links are specified by the user of the car navigation system. The proposed algorithm was implemented in C and experiments were performed upon the map that includes 64 nodes with 118 links. The experimental results show that the proposed algorithm is suitable to find preference-based shortest paths as well as distance shortest paths.

중소형 선박용 해양 네비게이션 시스템의 구현

김화업(Hwa-Up Kim),민병국(Byoung-Guk Min),하태진(Tae-Jin Ha),정희자(Hee-Ja Jeong),박종안(Jong-An Park) 한국정보기술학회 2013 한국정보기술학회논문지 Vol.11 No.3

In this paper, in order to solve the problem that path deviation can occur when small and medium sized power boats are operated, we have implemented a ship navigation system that it warns real-timely its condition in advance or that is guide the operation path from the deviated to the destination in the cases. The proposed navigation system consists of a main path and an sub-path. The sub-path gets the functions that prevents the ship to deviates by noticing in advance the places that can deviate the path, or that let it return the ship to the main path by guiding in the case that it deviates the path. This algorithm improves convenience and safety of small and medium sized power boats as it shorten the time to take from the deviated path to the destination path and the time to take for transferring information.

3D게임에서 이동 장애물을 고려한 동적 경로 탐색 기법

권오익,황보택근 한국게임학회 2006 한국게임학회 논문지 Vol.6 No.3

게임 인공지능 분야중 하나인 경로탐색은 좀더 사실적인 게임을 만들기 위한 중요한 요소이다. 경로탐색 시스템은 한정된 자원을 소비해야만 하는 제약사항 때문에 때때로 단순하게 처리되어 사실적이지 못한 경로를 생성하였다. 기존 연구에서는 정적인 지형과 장애물들을 이용하여 자연스럽게 회피하는 경로생성에 집중하였다. 하지만, 게임 공간에서는 다양한 종류의 움직이는 장애물들이 존재한다. 따라서 이러한 움직이는 장애물을 자연스럽게 회피하는 경로를 생성하는 시스템 이 필요하다. 본 논문에서는 네비게이션 메시(Navigation Mesh)로 공간을 표현하며 지형의 특성을 고려한 경로 탐색 방법을 적용하고, 움직이는 물체를 회피하기 위하여 지능적인 밀개와 끌개의 방법을 사용하여 경로 탐색을 수행한다. 제안된 시스템을 통하여 생성된 경로를 살펴보고 실제 게임에서의 활용성을 검증한다. Path-finding, one of the traditional Game A.I. problems, becomes an important issue to make games more realistic. Due to the limited resources in the computer system, path-finding systems sometimes produce a simplified and unrealistic path. The most relent researches have been focused on the path-finding avoiding only static obstacles. Various moving obstacles are however deployed in real games, a method avoiding those obstacles and producing a smooth path is necessary. In this paper, navigation mesh is used to represent 3D space and its topological characteristics are used for path-finding. Intellectual repulser and attractor are also used to avoid moving obstacles and to find an optimal path. We have evaluated the path produced by the method proposed in this paper and verified its usability in real game.

내비게이션 자료를 활용한 중장거리 경로 선택 행태 분석

남호현(NAM, Hohyeon),김익기(KIM, Ikki),김지혜(KIM, Jihye),유한솔(YOO, Hansol),박상준(PARK, Sangjun) 대한교통학회 2021 대한교통학회지 Vol.39 No.2

통행자의 경로 선택 행태 분석은 교통정책 수립, 장래 수요 예측단계 등에서 필요하지만 자료 취득의 어려움으로 인하여 분석의 한계점이 있었다. 특히 확률적 경로 선택 방법은 통행자의 선택 행태를 모형에 반영할 수 있지만 필수자료인 대안 경로 집합 구축에 어려움이 있다. 그러므로 본 연구는 대규모 표본 자료인 내비게이션 자료를 이용하여 경로 선택 모형을 구축하고 통행자의 경로 선택 행태 분석을 수행하였다. 경로 선택 모형은 다항 로짓 모형이 가지는 IIA 특성으로 인하여 발생하는 대안 경로 간 경로 겹침 문제를 극복하고 현실적 경로 선택 행태를 가능한 반영할 수 있는 Path-size 로짓 모형을 이용하였다. 본 연구는 통행의 기종점을 시군구 단위로 집합화하고 통행거리가 100km이상의 중장거리 경로 선택 행태를 설명하였다. 모형 정산 결과에서 거리 당 요금, 고속도로 이용거리, 총 통행거리가 설명변수로 입력되었으며 통계적으로 가장 유의한 모형을 도출하였다. 또한 모형의 통계적 설명력이 가장 높은 PS 변수를 황금분할법을 이용하여 산정하고 설명변수로 추가하였다. 모형에서 통행자들은 고속도로 구간의 길이가 더 길수록 해당 통행 경로를 더 선호하는 행태를 나타내었으며, 경로 내 고속도로 이용거리가 증가할 때보다 고속도로 외 도로의 이용거리가 증가할 때 민감하게 반응하였다. 모형의 정확성 검증을 위해 내비게이션 자료를 이용하여 관측 경로 선택 비율과 예측 경로 선택 확률을 계산하고 통행 경로 내 고속도로 이용 비율 별 평균 오차율을 산출하였다. 그 결과 고속도로 이용비율이 증가할수록 오차율은 감소하였다. The analysis of the route choice behavior is necessary in the stages of establishing transportation policies and forecasting travel demand, but there was a limitation due to the difficulty of collecting data. Especially, the stochastic route choice method can reflect the route choice behavior in the model. However it is difficult to collect data of the alternative path sets, which are essential for stochastic route choice method. Therefore this study calibrated route choice model with navigation data which is huge sample data to overcome sampling error. The route choice model is calibrated using path-size logit model that can explain passenger behavior and overcomes overlapping problem between alternative paths which is occurred due to the IIA property of multinomial logit model. This study researched the route choice behavior for travel of mid- to long-distance by aggregating the origin and destination as regional level zone. The most statistically significant route choice model was calculated and the fare per distance, highway travel distance, and total travel distance were used as explanatory variables. In addition, the PS variable with the highest statistical explanatory power of the model was calculated using golden-section search and added as an explanatory variables in route choice model. In the model, the longer the highway in the route, the more the passengers preferred it. And the passengers were more sensitive when the travel distance of road except highway in route were increased than when the travel distance of highway in route were increased. To verify accuracy of prediction of model, this study compared the observed route choice ratio and the predicted route choice probability which were calculated using navigation data. As a result, the average error rate decreased as highway length in travel distance was increased.

Path Planning for Autonomous Mobile Robot Based on Safe Space

Jong-Hun Park,Uk-Youl Huh 대한전기학회 2016 Journal of Electrical Engineering & Technology Vol.11 No.5

Path planning is essential for the autonomous navigation of mobile robots. Researchers have been working on ensuring the safe navigation of mobile robots; however, it is impossible to secure the absolute safety of a mobile robot without environmental information. Nevertheless, passive safety of a mobile robot can be secured. With the aim of ensuring safe path planning of a mobile robot, a safety space is proposed in this work by using the parameters of stopping distance and hazard point. Mobile robots should formulate path plans to bypass crossroads or corner areas where their field of view is limited, and they should also be capable of reducing their movement speed to secure safe driving. We demonstrate through extensive simulations that the developed SGPP (safe global path planning) method outperforms the classical A<SUP>*</SUP> and PRM (probabilistic roadmap) algorithms. It improves the navigation time and length of the robot path in comparison to the PRM algorithm and reduces the navigation time by up to 26% compared to the classical A<SUP>*</SUP> algorithm for safe navigation. In addition, results of an experiment conducted on a real robot show that the SGPP method finds a safe path with limited velocity for safe navigation.

무인운전차량의 자율주행을 위한 경로점 기반 경로계획

송광열(Gwang-Yul Song),이준웅(Joon-Woong Lee) 제어로봇시스템학회 2014 제어·로봇·시스템학회 논문지 Vol.20 No.2

This paper addresses an algorithm of path planning for autonomous driving of a ground vehicle in waypoint navigation. The proposed algorithm is flexible in utilization under a large GPS positioning error and generates collision-free multiple paths while pursuing minimum traveling time. An optimal path reduces inefficient steering by minimizing lateral changes in generated waypoints along a path. Simulation results compare the proposed algorithm with the A* algorithm by manipulation of the steering wheel and traveling time, and show that the proposed algorithm realizes real-time obstacle avoidance by quick processing of path generation, and minimum time traveling by producing paths with small lateral changes while overcoming the very irregular positioning error from the GPS.