A*와 최적화 기반 경로계획기법을 활용한 무인이동체의 자율주행

신종호(Jongho Shin),김민극(Mingeuk Kim) 대한기계학회 2022 大韓機械學會論文集A Vol.46 No.4

일반적으로 무인이동체는 자율주행 시 다양한 정적 및 동적 불확실성을 마주하게 된다. 이러한 불확실성에 의한 성능 저하를 극복하기 위해서는 주변의 환경을 고려한 최적의 경로가 필요하다. 하지만, 무인이동체가 주행하는 환경에 대한 정보를 미리 확보하는 것은 불가능하기 때문에, 기확보 가능한 수준에서 거시적 경로를 생성(광역 경로계획)하고, 실시간으로 확보되는 정보를 고려한 국지적 영역에서의 최적 경로(지역 경로계획)가 필요하다. 이에 본 논문에서는 A* 및 최적화 기법을 활용한 광역/지역경로계획 기법을 제안한다. A* 기반 광역 경로계획은 기확보 가능한 항공 혹은 위성사진을 활용하여 출발지로부터 목적지까지의 개략적인 경로를 생성한다. 광역 경로계획은 실제 환경의 다양한 불확실성 정보를 반영하지 못하므로, 무인이동체 주변의 실 환경 정보를 고려하는 최적 경로 생성이 요구된다. 이에 본 논문에서는 최적화 기법을 활용한 경로계획 기법을 제안한다. 최적화 기반 경로계획 기법은 무인이동체의 동역학 모델 및 이동 장애물, 등식/부등식 구속조건을 고려한 경로 생성을 가능하게 한다. 제안된 기법의 타당성을 검증하기 위하여, 정적 및 동적 장애물이 존재하는 환경을 기반으로 시뮬레이션을 수행하고 결과를 고찰한다. Generally, unmanned vehicles (UVs) face various static and dynamic uncertainties during autonomous navigation. To overcome those obstacles, the UV requires optimal path generated by considering the UV’s own environment. Because it is not possible to obtain information of the UV’s own environment in advance, global path should be generated first with obtainable environment information (GPP: global path planning) and then, local path for following the global path should be planned with realtime environment information (LPP: local path planning). This study proposes path planning methods with A* and optimization-based path planning algorithms. The GPP is performed using A* algorithm with offline developed map such as aerial or satellite photos. On the other hand, the optimization-based path planning is developed with kinematics/dynamics of the UV, equality/inequality constraints and real-time static/dynamic obstacle maps generated by sensors of the UV. To validate the performance of the proposed method, numerical simulations are performed and the results are analyzed.

동적 환경에서 그룹 이동을 위한 경로 계획

유견아(Kyeonah Yu),조수진(Su-Jin Cho) 한국컴퓨터정보학회 2013 韓國컴퓨터情報學會論文誌 Vol.18 No.2

가상의 캐릭터가 이동하기 위해 경로를 계획하는 일은 컴퓨터 게임을 포함한 여러 응용 분야에서 필수적인 문제이다. 기존의 로봇 경로 계획과는 달리 하나 이상의 캐릭터가 그룹 이동을 하는 경우가 많으며 이 경우에는 이동 경로의 최단 여부보다는 자연스러운 그룹 이동 등의 질적인 면이 강조된다. 본 논문에서는 리더로 정해진 단일 캐릭터에 대해 정적인 환경에서의 전역 경로를 계획하고 이 경로를 따라 그룹이 이동하며 동적 장애물을 피하도록 지역 경로를 계획하는 2단계 경로 계획 방법을 제안한다. 그룹이 이동할 수 있는 공간은 리더를 중심으로한 정방형 격자 배열을 이용하여 확보하고 이를 격자창이라고 부른다. 멤버 캐릭터들은 격자창 공간 안에서 리더에 대한 상대적인 위치를 잡아 이동하며 격자창이 이동할 수 있는 경로를 계획하기 위해 정적 환경을 격자창에 대한 형태 공간으로 치환하여 로드맵을 구한다. 지역 경로 계획 단계에서는 리더에 대해 인공 포텐셜 필드를 이용하여 동적 장애물을 회피하도록 하고 나머지 멤버들에 대해서는 격자창 내에서 리더에 대한 상대적인 위치를 확보하는 방법으로 연산량을 줄인다. 제안하는 경로 계획 방법을 구현하기 위한 효율적인 알고리즘을 소개하며 정적 환경에서 계획된 경로를 따라 그룹이 이동하면서 동적 장애물에 대해 효과적으로 대처하는 것을 시뮬레이션을 통해 보여 준다. Path planning is an essential problem to make virtual characters navigate in many applications including computer games. In many cases, multiple characters move in a group and qualitative aspects of planned paths are emphasized rather than optimality unlike Robotics. In this paper, we propose a two-level path planning algorithm in which the global path is planned for a single character specified as a leader and then the local path is planned to avoid dynamic obstacles while the group following this path. The space for group movement is achieved in the form of square grid array called a grid window. Member characters are located relatively to the leader within a space and moved. The static environment is reduced to the configuration space of this grid window to generate a roadmap on which a grid window can move. In local path planning, only the leader avoids dynamic obstacles by using an artificial potential field and the rest of members are located relatively to the leader in the grid window, which reduces computational load. Efficient algorithms to implement the proposed planning methods are introduced. The simulation results show that a group can handle with dynamic obstacles effectively while moving along the planned path for a static environment.

Theta*와 최적의 Bézier 곡선을 이용한 통합 경로계획

전준,신종호 대한기계학회 2024 大韓機械學會論文集A Vol.48 No.1

본 논문는 Theta* 및 Piecewise Bézier 곡선을 활용한 경로계획 기법을 제안한다. Theta*는 전방향 경로계획으로 기확보된 지도 내에서 무인 이동체의 초기위치로부터 목표점까지의 경로를 생성한다. 그러나 이는 실시간으로 반영되는 새로운 정보를 고려하지 않는다. 이를 위해, 본 논문에서는 실시간으로 주변 환경 및 무인 이동체의 특성, 생성한 경로의 곡률, 광역경로점 추종성을 고려한 최적화 기반 경로계획 기법을 제안한다. Spiral optimization을 활용하여 최적화 문제의 해를 찾아 Piecewise Bézier 곡선의 최적 제어점을 생성한다. ROS(robot operating system)과 Gazebo를 활용한 가상환경 시스템을 구축하고, 제안된 기법의 타당성을 검증하기 위한 시뮬레이션 수행 및 결과를 분석한다. This paper proposes a path planning technique using Theta* and Piecewise Bézier curves. Theta* creates a path from the initial position of an unmanned vehicle to a target point within a map secured a priori by omnidirectional path planning. However, this does not take into account new information reflected in real time. To this end, in this paper, we propose an optimization-based path planning technique that considers the characteristics of the surrounding environment and unmanned mobile vehicle, curvature of the generated path, and followability of global path in real time. The solution of the optimization problem is obtained using spiral optimization, and the optimal control point of the Piecewise Bézier curve is generated using the solution. A virtual environment system is developed with the robot operating system (ROS) and Gazebo. Finally, numerical simulations are performed to verify the validity of the proposed technique, and the results are analyzed.

경로 추종 적합성 고려 3D A* 기반 접안 경로 계획 알고리즘 개발

신영하(Yeong-Ha Shin) 한국항해항만학회 2022 한국항해항만학회 학술대회논문집 Vol.2022 No.2

선박의 운항 경로를 생성하기 위해 사용되는 경로 계획 방법 중, 그래프 기반 탐색 방식은 간결하고 최적해를 보장한다는 장점이있어 널리 사용되고 있다. 그래프 기반 탐색 방식을 접안 경로 계획에 적용하는 경우, 추종 적합성을 필수적으로 고려 해야 한다. 그 이유는접안 시 경로 이탈은 접안 시설과의 충돌로 이어질 수 있으므로, 경로의 이탈이 최소화하는 결과를 생성하는 것이 필요하다. 하지만 그래프 탐색 기반 접안 경로 계획의 기존 연구는 접안 시설 직전의 변침이 많은 결과를 생성하기 때문에 실제 운항 환경에 적용하는데 위험이 존재한다. 따라서 본 논문에서는 경로 추종에 적합한 비용 함수를 개발하고, 이를 적용한 3D A* 알고리즘을 제안한다. 또, 실제 운항 환경에 대한 적합성을 평가하기 위해서 유인 운항으로 수집한 데이터의 항적과 알고리즘의 경로 생성 결과를 비교한다. Among the path planning methods used to generate the ship's path, the graph search-based method is widely used because it has the advantage of its completeness, optimality. In order to apply the graph-based search method to the berthing path plan, the deviation from the path must be minimized. Path following suitability should be considered essential, since path deviation during berthing can lead to collisions with berthing facilities. However, existing studies of graph search-based berthing path planning are dangerous for application to real-world navigation environments because they produce results with a course change just before berthing. Therefore, in this paper, we develop a cost function suitable for path following, and propose a 3D A* algorithm that applies it. In addition, in order to evaluate the suitability for the actual operating environment, the results of the path generation of the algorithm are compared with the trajectory of the data collected by manned operations.

급속탐색랜덤트리기법 기반의 무인 비행체 경로계획생성 최적화 연구

봉재환(Jae-Hwan Bong),정성균(Seong-Kyun Jeong) 한국전자통신학회 2023 한국전자통신학회 논문지 Vol.18 No.5

무인 비행체의 활용범위가 확대됨에 따라 관련 기술의 발전과 기술 수요도 증가하는 추세이다. 무인 비행체의 운영빈도가 늘어나고 운영의 편리성이 강조됨에 따라 관련 자율비행 기술도 중요성이 주목받고 있다. 무인 비행체의 자율 비행에 있어 목적지에 도달하는 경로계획을 세우는 일은 유도제어에서 중요하며 무인화의 효과를 극대화하기 위해서는 경로계획 역시 자동으로 생성하는 기술이 필요하다. 본 논문에서는 무인 비행체의 자율운영 효과를 높이기 위해서 급속탐색랜덤트리기법으로 생성된 경로를 무인기의 특성에 맞게 최적화하는 기법에 관한 연구를 수행하였다. 최적 거리, 최단 시간, 임무점 통과 등의 지표를 달성하기 위해 경로계획을 무인 비행체의 임무 목표와 동적 특성을 고려하여 최적화하였다. 제안한 기법은 장애물 상황에 대한 성능 검증을 통해 무인 비행체 경로계획 생성에 적용 가능성을 확인하였다. As the usage of unmanned aerial vehicles expands, the development and the demand of related technologies are increasing. As the frequency of operation increases and the convenience of operation is emphasized, the importance of related autonomous flight technology is also highlighted. Establishing a path plan to reach the destination in autonomous flight of an unmanned aerial vehicle is important in guidance and control, and a technology for automatically generating path plan is required in order to maximize the effect of unmanned aerial vehicle. In this study, the optimization research of path planning using rapid-exploring random tree method was performed for increasing the effectiveness of autonomous operation. The path planning optimization method considering the characteristics of the unmanned aerial vehicle is proposed. In order to achieve indexes such as optimal distance, shortest time, and passage of mission points, the path planning was optimized in consideration of the mission goals and dynamic characteristics of the unmanned aerial vehicle. The proposed methods confirmed their applicability to the generation of path planning for unmanned aerial vehicles through performance verification for obstacle situations.

동적 변화 환경에서 다중 임무점 방문을 위한 최적 경로 계획 알고리즘

이호형(Hohyeong Lee),장우혁(Woohyuk Chang),장환철(Hwanchol Jang) 한국항공우주학회 2019 韓國航空宇宙學會誌 Vol.47 No.5

다중 임무점 방문을 위한 경로 계획의 복잡도는 단일 구간 경로 계획을 위한 복잡도보다 크게 더 높다. n개의 다중 임무점을 방문하는 경로 계획을 위해서는 n<SUP>2</SUP>+n번의 단일 구간 경로 계획이 필요하다. 본 논문에서는 동적 변화 환경에서 다중 임무점을 방문하기 위한 최적의 경로 계획 알고리즘인 Multiple Mission D<SUP>*</SUP> Lite(MMD<SUP>*</SUP>L) 알고리즘을 제안하였다. MMD<SUP>*</SUP>L은 앞서 수행된 단일 구간 경로 계획 정보를 재사용함으로써 복잡도를 감소시킨다. 시뮬레이션 결과를 통해 경로의 최적성은 양보하지 않으면서도 복잡도가 급격하게 감소하였음을 확인하였다. The complexity of path planning for visiting multiple mission points is even larger than that of single pair path planning. Deciding a path for visiting n mission points requires conducting n<SUP>2</SUP>+n times of single pair path planning. We propose Multiple Mission D<SUP>*</SUP> Lite(MMD<SUP>*</SUP>L) which is an optimal path planning algorithm for visiting multiple mission points in dynamic environments. MMD<SUP>*</SUP>L reduces the complexity by reusing the computational data of preceding single pair path planning. Simulation results show that the complexity reduction is significant while its path optimality is not compromised.

큰 맵에 적용가능한 확장된 BSA 커버리지 알고리즘

미아오쉬(Xu Miao),이현순(Hyun-Soon Lee),강보영(Bo-Yeong Kang) 한국지능시스템학회 2017 한국지능시스템학회논문지 Vol.27 No.5

본 논문에서는 청소 로봇이 미지의 큰 맵에 대해 맵-분해를 적용할 수 있는 확장된 BSA(backtracking spiral algorithm) 커버리지 경로계획(coverage path planning)을 제안한다. 기존의 나선형 경로에 기반한 방법은 전체 맵을 로봇의 크기만큼 나누고 각 격자에서 맵 정보를 기록한 격자들을 통해서 청소 맵에 대한 커버리지 경로계획을 구현할 수 있지만 격자 수량이 많을수록 알고리즘의 성능이 떨어지는 단점이 존재한다. 제안한 방법은 큰 맵에서 맵 축소 및 A* 탐색 기법을 이용하여 맵을 분해하고 맵의 크기 조절을 통해서 격자의 수량을 효율적으로 제어할 수 있기 때문에 기존의 방법의 단점을 극복할 수 있을 뿐만 아니라 분해된 작은 맵에서 기존의 BSA기법을 사용하여 나선형 경로에 기반한 커버리지 경로계획의 장점도 유지할 수 있다. 일련의 실험을 통하여 제안된 방법은 미지의 큰 맵에서 커버리지 경로계획을 보다 효과적으로 적용이 가능하였고, 기존의 BSA 기법의 성능을 효율적으로 개선할 수 있었다. In this paper we propose an extended BSA (Backtracking Spiral Algorithm) which uses coverage path planning method for map-decomposition of large unknown maps. The existing spiral path planning method divides the entire map into grids by the size of the cleaning robot and stores the grid information which is then used to generate the cleaning path. The main disadvantage of this existing method is that when the size of map increases the grid information necessary to complete the cleaning path generation also increases which is less efficient. The proposed method thus overcomes the disadvantages of existing method by effectively controlling the size of map to form a contracted map and by using A* method for map-decomposition. As the proposed method can effectively control the number of grid it not only overcomes the disadvantages of the existing spiral path planning method but also maintains the advantages of using BSA in the decomposed map. Through a series of experiments it was found that the proposed method can effectively apply the coverage path planning in large unknown maps and improve the performance of the existing BSA method.

예측 행태를 고려한 보행자 경로 계획 모형

김정윤,여화수 대한교통학회 2019 대한교통학회지 Vol.37 No.5

Recently, interest in planning and operating the walking environment is increasing along with sustainable transportation. The need for pedestrian behavior research is also increasing in that it evaluates the walking environment and establishes criteria for improvement. The pedestrian path planning behavior model proposed in this paper is distinguished from the existing models in that it represents pedestrians’ anticipation behavior with realistic assumptions and applies the anticipation behavior to the path planning behavior. Expected occupancy map (EOM) is developed to estimate the future walking environment assuming that pedestrians anticipate changes in walking environment based on the current position and speed of surrounding pedestrians. Based on the EOM, the travelers choose their optimal path considering the safety and travel time. The path planning problem is formulated to minimize the total travel delay, and it is solved using the Genetic Algorithm. First, we verify the proposed model and analyze the effect of collision penalty on the path planning. Then, we compare the movements of pedestrians with and without anticipation by combining the micro model and the proposed model. The results show that the pedestrian anticipation can reduce the travel distance and the collision probability. 최근 지속 가능한 교통수단과 함께 보행환경에 대한 관심도 커지고 있다. 보행자 행태 연구는 보행환경의 계획, 조성, 평가, 개선을 포함하는 일련의 과정에 대한 기준과 근거를 만든다는 점에서 그 필요성도 함께 증가하고 있다. 본 논문이 제안하는 보행자 경로 계획 행태 모형은 보행환경 변화를 예상하는 행태를 현실적인 가정을 기초로 모형화하고 이를 경로 계획 행태에 적용했다는 점에서 기존 모형들과의 차별성을 지닌다. 보행자가 주변 보행자들의 현재 위치와 속도 정보로 보행환경 변화를 예상한다는 가정으로 미래 보행환경 예상 점유 지도를 개발하였으며, 이를 토대로 계획 경로들의 예상 충돌 확률을 산정한다. 최적 경로는 이동 거리와 예상 충돌 확률을 최소화하는 경로로 정의되며, 이는 유전자 알고리즘을 통해 산출된다. 실험에서는 충돌 영향력 크기에 따른 계획 경로 산출 결과를 통해 충돌 영향력과 경로의 길이 및 충돌 확률 간의 관계를 확인하고, 제안하는 경로 계획 모형에 대표적인 충돌 방지 보행 모형인 힘 기반 보행 모형을 적용한 시뮬레이션 결과를 통해 보행환경 변화를 예상하는 행태가 보행자의 이동 거리를 줄이면서도 충돌 확률을 낮추는 역할을 하는 것을 검증한다.

군집로봇의 협조 탐색을 위한 최적 영역 배치

방문섭(Mun Seop Bang),주영훈(Young Hoon Joo),지상훈(Sang Hoon Ji) 한국지능시스템학회 2012 한국지능시스템학회논문지 Vol.22 No.6

본 논문에서는 군집로봇의 효과적인 협조탐색을 위한 탐색영역에 대한 군집로봇의 최적배치을 제안한다. 먼저, 탐색영역에대한 최적의 배치를 위해 보로노이 테셀레이션과 K-mean 알고리즘을 이용하여 탐색영역을 분할한다. 분할된 영역을 안전한 주행을 위해 전역경로계획과 지역경로계획을 한다. 전역경로계획은 A*알고리즘을 이용하여 전역경로계획을 하여 최적의 전역경로를 찾고, 지역경로계획은 포텐셜 필드방법을 이용하여 장애물 회피 통해 안전하게 목표점에 이르게 한다. 마지막으로 제안한 알고리즘은 시물레이션을 통해 그 응용가능성을 검토한다. In this paper, we propose a optimal deployment method for cooperative exploration of swarm robots. The proposed method consists of two parts such as optimal deployment and path planning. The optimal area deployment is proposed by the K-mean Algorithm and Voronoi tessellation. The path planning is proposed by the potential field method and A* Algorithm. Finally, the numerical experiments demonstrate the effectiveness and feasibility of the proposed method.

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

김동욱(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.