Tour generation of heterogeneous nonholonomic sensor platforms = 비홀로노믹 복수 이종 센서 플랫폼의 경로 생성

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 363
  • Download : 0
This thesis addresses a formulation and develops novel approaches to solve a nonholonomic path planning problem for a group of heterogeneous unmanned aerial vehicles (UAVs) with capabilities of executing tasks remotely in a two-dimensional environment. The purpose of the path planning problem is to find an appropriate tour for each vehicle with minimum costs such that all the tasks in the mission are visited by one of the vehicles. In general, each vehicle has different motion constraints and is located at different points when starting the mission. A sum of two terms, the normalized sum of the total tour cost and the largest cost tour among the vehicles, is used as the objective function to be minimized. In particular, the proposed algorithms are structured to obtain high performance with considering the motion constraints of the vehicles when the tasks are closely located. The problem is formulated as a Mixed-Integer Linear Programming (MILP) based on the sampling-based roadmap, and three different approaches are proposed: a) the main ingredient of a branch-and-cut algorithm to compute the optimal solution; b) the transformation method which changes the given problem instance into the form of asymmetric traveling salesman problem to use the Lin-Kernighan-Helsgaun heuristic; c) the memetic algorithm to obtain the the near-optimal solution. After obtaining solutions from the above approaches, the path refinement process is applied to locally optimize the obtained solution. Comparative numerical experiments show the validity and efficiency of the proposed methods compared with the previous methods. In addition, the transformation method is utilized in an observation task scheduling of a heterogeneous satellite constellation orbiting in the low-Earth-orbit area. The purpose of the problem is to find a scheduling output that maximizes the sum of profits while following all of the constraints originating from the complex mission environment. The scheduling problem is modeled as an instance of asymmetric traveling salesman problem (ATSP), and then solved using the Lin-Kernighan-Helsgaun algorithm available for the ATSP. Numerical experiments are designed to show the characteristics, efficiency, and scalability of scheduling results which has an improvement of up to 20% in the sum of profits and the number of assignments over the first-in/first-out strategy-based greedy algorithm.
Choi, Han-Limresearcher최한림researcher
한국과학기술원 :항공우주공학과,
Issue Date

학위논문(박사) - 한국과학기술원 : 항공우주공학과, 2019.2,[vi, 118 p. :]


Path planning▼ageneralized heterogeneous multiple depot asymmetric traveling salesman problem▼aexact algorithm▼atransformation method▼amemetic algorithm▼aUAV task assignment▼aremote sensing▼aLEO satellite constellation▼aobservation scheduling; 경로 계획▼a다수 이종 비대칭 이웃 외판원 문제▼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