http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
No-depot minmax mTSP 문제를 위한 분할 및 가변 이웃 탐색 기반 휴리스틱
김민유,유태영,홍성현,정상수 한국과학영재교육학회 2023 과학영재교육 Vol.15 No.3
본 연구에서는 no-depot minmax mTSP를 해결하는 SlGi 휴리스틱을 제안한다. SlGi 휴리스틱은 구성 단계와 개선 단계로 구성된다. 각 단계에 사용되는 k-slice method 알고리즘과 SAG-insertion 알고리즘을 제안한다. k-slice method와 선행연구에서 제시한 클러스터링 알고리즘을 비교한 결과, k-slice method가 여러 데이터에서 선행연구 알고리즘보다 뛰어난 성능을 보임을 확인하였다. 또한, SlGi 휴리스틱을 이용해 구한 minmax 거리와 ES, MILP 알고리즘을 이용한 minmax 거리, 최적 minmax 거리를 비교하였다. 그 결과, SlGi 휴리스틱이 선행연구 알고리즘 및 알려진 최적해와 비슷한 수준의 minmax 거리를 구하는 것을 확인하였다. SlGi 휴리스틱은 외판원의 수가 증가할수록 알려진 최적해와의 차이가 감소하며, 실행 시간 또한 줄어든다. 따라서 외판원의 수가 더 많은 경우에 더욱 준수한 성능을 보일 것으로 예상된다. In this study, we present the SlGi heuristic to address the no-depot minmax mTSP, comprising both construction and improvement stages. For each stage, we introduce a k-slice method algorithm and a SAG-insertion algorithm. Comparative analysis against clustering algorithms reveals the superior performance of the k-slice method across various data sets. Additionally, we compare minmax distances obtained using the SlGi heuristic with those from ES and MILP algorithms, as well as the optimal minmax distance. Results show that the SlGi heuristic achieves comparable minmax distances to algorithms in the literature and the known optimal solution. Notably, differences between the SlGi heuristic and the known optimal solution decrease with an increasing number of salesmen, accompanied by reduced execution time. Thus, the SlGi heuristic is expected to perfom better with a larger number of salesmen.
Robustness for Scalable Autonomous UAV Operations
정성훈,Kartik B. Ariyur 한국항공우주학회 2017 International Journal of Aeronautical and Space Sc Vol.18 No.4
Automated mission planning for unmanned aerial vehicles (UAVs) is difficult because of the propagation of several sources of error into the solution, as for any large scale autonomous system. To ensure reliable system performance, we quantify all sources of error and their propagation through a mission planner for operation of UAVs in an obstacle rich environment we developed in prior work. In this sequel to that work, we show that the mission planner developed before can be made robust to errors arising from the mapping, sensing, actuation, and environmental disturbances through creating systematic buffers around obstacles using the calculations of uncertainty propagation. This robustness makes the mission planner truly autonomous and scalable to many UAVs without human intervention. We illustrate with simulation results for trajectory generation of multiple UAVs in a surveillance problem in an urban environment while optimizing for either maximal flight time or minimal fuel consumption. Our solution methods are suitable for any well-mapped region, and the final collision free paths are obtained through offline sub-optimal solution of an mTSP (multiple traveling salesman problem).
Robustness for Scalable Autonomous UAV Operations
Jung, Sunghun,Ariyur, Kartik B. The Korean Society for Aeronautical and Space Scie 2017 International Journal of Aeronautical and Space Sc Vol.18 No.4
Automated mission planning for unmanned aerial vehicles (UAVs) is difficult because of the propagation of several sources of error into the solution, as for any large scale autonomous system. To ensure reliable system performance, we quantify all sources of error and their propagation through a mission planner for operation of UAVs in an obstacle rich environment we developed in prior work. In this sequel to that work, we show that the mission planner developed before can be made robust to errors arising from the mapping, sensing, actuation, and environmental disturbances through creating systematic buffers around obstacles using the calculations of uncertainty propagation. This robustness makes the mission planner truly autonomous and scalable to many UAVs without human intervention. We illustrate with simulation results for trajectory generation of multiple UAVs in a surveillance problem in an urban environment while optimizing for either maximal flight time or minimal fuel consumption. Our solution methods are suitable for any well-mapped region, and the final collision free paths are obtained through offline sub-optimal solution of an mTSP (multiple traveling salesman problem).
IT Convergence UAV Swarm Control for Aerial Advertising
Sunghun Jung 한국융합학회 2017 한국융합학회논문지 Vol.8 No.4
소형 무인항공기의 가격이 저렴해지고 제어가 쉬워짐에 따라, 고정익 또는 회전익 무인항공기를 사용하는 항공 어플리케이션이 최근 많이 등장하였다. 본 논문에서는 4대의 회전익 무인항공기를 사용한 새로운 공중 광고법 이 제안되었다. 무인항공기 군집 제어를 통해, 4대의 무인항공기가 7.07 × 7.07 m2 사이즈의 정사각형 현수막을 사 전에 정의된 비행경로를 따라 운반하며 공중 광고를 한다. 시뮬레이션 결과에 따르면, 무인항공기들이 669 × 669 m2 크기의 영역에서 전체를 비행하며 공중 광고를 수행하는 데는 총 270 s 가 소요되며, 무인항공기들 사이의 최소 거리는 0.45 m 로서 충돌이 발생하지 않음이 밝혀졌다. 몇몇 급격한 방향 전환이 필요한 경로로 인하여 무인항공기 들이 정확한 정사각형 군집 비행을 수행하기 어려운 구간이 있으며, 이때 정사각형 편대 비행의 최대 및 최소 변의 길이는 10.35 m와 1.96 m로 밝혀졌다. 또한, 정사각형 편대 비행의 최대 및 최소 대각선 길이는 각각 14.75 m와 2.78 m로 파악되었다. As the price of small UAVs is getting cheaper and its controllability is getting greatly increased, many aerial applications using both fixed-wing and hoverable UAVs have appeared in recent years. In this paper, a new aerial advertising method is proposed using four hoverable UAVs. Using the UAV swarm control method, four UAVs are maneuvered to carry a 7.07 × 7.07 m2 square banner along collision-free and predefined waypoints for aerial advertising. According to simulation results, it takes about 270 s for UAVs to perform aerial advertising in 669 × 669 m2 size area and the minimum distance among UAVs turns out to be 0.45 m which proves there is no any collision. Due to abrupt direction changes of UAVs along the predefined waypoints, UAVs cannot always maintain exact square formation and it results the maximum and minimum side lengths of square formation to be 10.35 m and 1.96 m, respectively. Also, the maximum and minimum diagonal lengths of square formation turn out to be 14.75 m and 2.78 m, respectively.