Earticle

This research is to select a path planning algorithm to maximize survivability for Unmanned Aerial Vehicle(UAV). An UAV is a powered pilotless aircraft, which is controlled remotely or autonomously. UAVs are currently employed in many military missions(surveillance, reconnaissance, communication relay, targeting, strike etc.) and a number of civilian applications(communication service, broadcast service, traffic control support, monitoring, measurement etc.). In this research, a mathematical programming model is suggested by using MRPP(Most Reliable Path Problem) and verified by using ILOG CPLEX. A path planning algorithm for UAV is selected by comparing of SPP(Shortest Path Problem) algorithms which transfer MRPP into SPP.

In order to address the issue of taxi carpooling path planning on urban roads, this study suggests an improved A^* algorithm and a model based on node weight. The path planning model enables us to implement carpool path planning after carpool passengers, taxi passengers, and taxi drivers have gathered. It uses a vector city traffic road network, city road vector map topology, dynamic road weight functions, node weight tables of the road, and an improved A^* algorithm. Our evaluation of the model involves comparing its path planning computation time and total travel time with the traditional A^* algorithm using Nanjing taxi trajectory data. The comparison shows that the proposed algorithm significantly outperforms the traditional A^* algorithm. Results show that the taxi path planning model proposed in this paper can provide a reference for carpool passengers, taxi passengers, and taxi drivers in choosing a carpool.

Various modified algorithms of rapidly-exploring random tree (RRT) have been previously proposed. However, compared to the RRT algorithm for collision avoidance with global and static obstacles, it is not easy to find a collision avoidance and local path re-planning algorithm for dynamic obstacles based on the RRT algorithm. In this study, we propose boundary-RRT*, a novel-algorithm that can be applied to aerial vehicles for collision avoidance and path re-planning in a three-dimensional environment. The algorithm not only bounds the configuration space, but it also includes an implicit bias for the bounded configuration space. Therefore, it can create a path with a natural curvature without defining a bias function. Furthermore, the exploring space is reduced to a half-torus by combining it with simple right-of-way rules. When defining the distance as a cost, the proposed algorithm through numerical analysis shows that the standard deviation (σ) approaches 0 as the number of samples per unit time increases and the length of epsilon ε (maximum length of an edge in the tree) decreases. This means that a stable waypoint list can be generated using the proposed algorithm. Therefore, by increasing real-time performance through simple calculation and the boundary of the configuration space, the algorithm proved to be suitable for collision avoidance of aerial vehicles and replanning of local paths.

본 연구는 고난도 주차 환경에서 효과적인 경로계획을 지원하기 위해 강화학습을 활용한 효율적 중간 목표 도출을 통한 최적의 경로계획 알고리즘을 제안한다. 주차 공간이 넓고 장애 물이 적은 경우, 단순한 경로계획 알고리즘으로도 최적의 경로를 생성할 수 있다. 하지만 차량 의 논홀로노믹 시스템으로 인해 복잡하고 좁은 환경에서는 장애물 등으로 인해 최적 경로를 보장하기 어렵다. 이를 해결하기 위해, 불필요한 탐색을 최소화하고 최적 경로로의 탐색을 유 도하는 중간 목표를 제안한다. 중간 목표는 하이브리드 A* 알고리즘의 휴리스틱 비용 계산의 기준점으로 활용되며, 강화학습을 통해 주차 환경에서 연산 효율성과 경로 품질을 극대화할 수 있는 지점으로 도출된다. 이러한 접근은 기존 휴리스틱 비용 산정의 비효율성을 극복하고, 최적 경로의 주요 지점을 효과적으로 탐색할 수 있도록 한다.

This paper proposes an optimal path planning algorithm designed to support effective path planning in challenging parking environments using reinforcement learning to derive efficient sub-goals. Although simple path planning algorithms can generate optimal paths in spacious parking environments with few obstacles, it becomes challenging to ensure optimal paths in complex and narrow environments because of the nonholonomic system of vehicles. The paper addresses this issue by suggesting sub-goals that can serve as key points for optimal paths. Sub-goals minimize unnecessary searches; and guide the path towards the optimal solution. Sub-goal were derived through reinforcement learning and used as heuristic cost criteria in the Hybrid A* algorithm to maximize computational efficiency and path quality. This approach overcomes the inefficiencies of conventional heuristic cost and facilitates effective explorations of the key points in the optimal path.

A new local path planning algorithm for free-ranging robots is proposed. Considering that a laser range finder has the excellent resolution with respect to angular and distance measurements, a simple local path planning algorithm is achieved by a directional weighting method for obtaining a heading direction of nobile robot. The directional weighting method decides the heading direction of the mobile robot by estimating the attractive resultant force which is obtained by directional weighting function times range data, and testing whether the collision-free path and the copen parthway conditions are satisfied. Also, the effectiveness of the established local path planning algorithm is estimated by computer simulation in complex environment.

본 논문에서는 로봇분야에서 사용되고 있는 경로계획 알고리즘에 대한 리뷰를 통하여 특징을 살펴보고자 한다. 경로계획 방법으로 셀 분해 방식, 로드맵 접근방식, 포텐셜 필드 방식을 살펴본다. 각 각의 장단점을 통하여 최적의 경 로계획에 대한 개선방향을 살펴보고자 한다.

This paper is a short review of path planning algorithm of mobile robot society. There are three big kinds of algorithm, cell decomposition method, robotmap method, and potential field method, are described. This review can present further direction of improvement of optimal path planning algorithm through merits and demerits.

In this study, a drone-based optimal path simulator was developed to evaluate four path finding algorithms-Dijkstra, A^*, D^* Lite, and C hristofides-for agricultural pest control missions. The simulator was tested under two spatial distribution conditions (scattered and clustered) with varying numbers of target points (50, 100, and 150). Each algorithm was assessed using four performance metrics: energy consumption, total travel distance, simulation time, and path computation time. A weighted scoring system was applied to derive a comprehensive performance score. The simulation results showed that the Christofides algorithm consistently outperformed other algorithms in large-scale and complex environments, achieving perfect scores in scenarios with 100 and 150 target points, regardless of distribution type. The A^* algorithm exhibited balanced and effective performance in small-scale or clustered environments, particularly with 50 target points, and maintained moderate performance at medium scale. These findings highlight the importance of algorithm selection based on both spatial distribution and problem scale. The Christofides algorithm is recommended for large-scale optimization tasks, while A^* is suitable for small-scale or dense environments.

Optimal path planning refers to find the safe route to the destination at a low cost, is a major problem with regard to autonomous navigation. Sampling Based Planning(SBP) approaches, such as Rapidly-exploring Random Tree Star($RRT^*$), are the most influential algorithm in path planning due to their relatively small calculations and scalability to high-dimensional problems. $RRT^*$-Smart introduced path optimization and biased sampling techniques into $RRT^*$ to increase convergent rate. This paper presents an improvement plan that has changed the biased sampling method to increase the initial convergent rate of the $RRT^*$-Smart, which is specified as m$RRT^*$-Smart. With comparison among $RRT^*$, $RRT^*$-Smart and m$RRT^*$-Smart in 2 & 3-D environments, m$RRT^*$-Smart showed similar or increased initial convergent rate than $RRT^*$ and $RRT^*$-Smart.

본 논문은 로봇 충돌회피 경로계획의 문제점을 해결하기 위해 진화된 모델에 근거한 새로운 경로탐색 전략을 소개한다. 최적화된 지능형 검색 방법으로 잘 알려진 유전자 알고리즘을 이용하여 로봇 경로계획 방법을 설계하였다. 염색체 안에 있는 유전자 인자로 경로점을 고찰해보면 주어진 맵에 대한 가능한 해법이제공된다. 생성된 염색체 간의 거리가 먼 경우 유사한 염색체에 대한 적합도로 간주할 수 있다. 경로계획에 있어 본 논문에서 제안한 유전자 알고리즘의 유효성을 증명하기위해 다양한 방법으로 시뮬레이션을 실시하였으며, 제안한 경로 검색 방법은 정지된 장애물이나 복잡한 장애물에도 사용될 수 있음을 증명하였다.

This paper presents a new search strategy based on models of evolution in order to solve the problem of collision-free robotic path planning. We designed the robot path planning method with genetic algorithm which has become a well-known technique for optimization, intelligent search. Considering the path points as genes in a chromosome will provide a number of possible solutions on a given map. In this case, path distances that each chromosome creates can be regarded as a fitness measure for the corresponding chromosome. The effectiveness of the proposed genetic algorithm in the path planning was demonstrated by simulation. The proposed search strategy is able to use multiple and static obstacles.

A reduced machining time and increased accuracy for the sculptured surface are very important when producing complicated parts. The step-size and tool-path interval are essential components in high speed and high resolution machining. If they are small, the machining time will increase, whereas if they are large, rough surfaces will be caused. In particular, the machining time, which is key in high speed machining, is affected by the tool-path interval more than the step-size. The conventional method for calculating the tool=path interval is to select a small parametric increment of a small increment based on the curvature of the surface. However, this approach also has limitations. The first is that the tool-path interval can not be calculated precisely. The second is that a separate tool-path interval needs to be calculated in each of the three cases. The third is that the conversion from Cartesian domain to parametric domain or vice versa must be necessary. Accordingly, the current study proposes a new tool-path interval algorithm that do not involve a curvature and that is not necessary for any conversion and a variable step-size algorithm for NURBS.

Path planning algorithm is a key issue among robot control areas. In practical engineering applications, traditional methods have some limitations to a certain degrees in key aspects of cost, efficiency, security, flexibility, portability, etc. Through the analysis and comparison of A-star algorithm and Dijkstra algorithm, path planning problem supporting multiple cars run parallely (PPSMC for short) in a static and dynamic obstacles co-existing environment is studied. An A-STAR-Dijkstra-integrated algorithm is promoted to make multiple cars moving parallely without collision or deadlock. Both two algorithms are optimized too. The algorithm has applied in smart park.

To address the problem that reactive navigation is prone to local optimality under uncertain and complex environments, a POMDP-based global path planning algorithm is proposed for mobile robots. A 6-tuple model is constructed for path planning under complex dynamic environments, and the global optimality is realizes by maximizing the accumulative reward function. State transition function and observation function are used to handle unknown obstacles and noisy perception by modeling the error probability. Belief state space is introduced, and a value iteration algorithm using point-based policy treepruning is developed to solve for real time planning policy, which effectively reduces the computational complexity. Simulation results show that using this algorithm the robot can automatically adapt to different probing granularities, avoid obstacles under complex uncertain environments, and achieve the optimal paths.

In order to solve the path planning problem about UAV attack multiple moving targets under dynamic environment, analytical method is proposed in this paper. Firstly, the Voronoi diagram method is used to create threat field, and the total planning cost is established. Then, the artificial potential field method and the dijkstra algorithm is improved and optimized respectively. For the track point outside the Voronoi diagram, the artificial potential field method is used to generate the local track. For the track point inside the Voronoi diagram, the dijkstra algorithm is used to track the moving target tracking along the side of Voronoi diagram, and the analytical method that UAV path planning method of moving target under dynamic environment is put forward. Finally, the simulation experiment is conducted, the result of simulation shows that the Voronoi diagram method can become complex airspace into division problems, the search space is reduced effectively, the time of planning is shorten, and the UAV real-time tracking and precision strikes against multiple moving targets can be resolved efficiently.

This paper focuses on the path planning for a mobile robot which is operated in indoor environment. Since the layout of indoor environment is a hybrid structure of known and unknown, this paper presents a hybrid algorithm which uses the Max-Q method and the option method together. Firstly, a novel task graph and high level definition are presented to divide sub-tasks. Then, the appropriate definitions of states, actions and options could let a robot fulfill a task. Finally, an angle parameter is employed in the reward function to ensure a robot select a shorter path and adjust orientation timely. In the series of simulations, a robot can arrival any position successfully with random initial positions and directions. Moreover the results show that a robot can overcome the local minimal problem with our hybrid method.

In this paper, we study the influence of the current on the selection of the cruise path of AUV (Autonomous Underwater Vehicle). We extended the current model into 3D space. According to this extended current model, we analyze AUV’s energy consumption under the affects of the water flow and compare it under different cruise paths. This study mainly focuses on the path optimization based on the current model and energy priority. To some extent, it provides a theoretical basis for the optimization of the AUV cruise path.

Group mobile robot path planning is a multi-objective optimization problem, as the requirement of obstacle avoidance, traditional robot path planning optimization method has the problem of algorithm complexity, large search space and low efficiency, it is difficult to obtain the optimal solution. In order to improve the efficiency and the positioning accuracy of group robot path planning, we put forward a group mobile robot path planning method based on variable dimension artificial bee colony algorithm. Firstly, we take robot working environment to model, then taking group robot path network as nectar source, the ultimate goal of path planning is to find minimal path network, to find an optimal swarm robot moving path network which avoids obstacles through the mutual cooperation between bees. Simulation experiment results show that the path planning method based on variable dimension artificial bee colony algorithm improves the efficiency of swarm robot path planning, it can find optimal solution of swarm robot path planning during the shortest time, and it can avoid obstacles safely, it provides basis to group robot task coordination.