應用於無人機包裹遞送任務之路線優化與深度強化學習防撞研究

簡易檢索 / 詳目顯示

回結果列表

研究生：	紀鈞元 CHUN-YUAN CHI
論文名稱：	應用於無人機包裹遞送任務之路線優化與深度強化學習防撞研究 Studies of Route Optimization and Deep Reinforcement Learning Based Collision Avoidance in UAV Parcel Delivery Tasks
指導教授：	蘇順豐 Shun-Feng Su 郭重顯 Chung-Hsien Kuo
口試委員:	蔡孟勳 Meng-Shiun Tsai 蕭得聖 Te-Sheng Xiao 李維楨 Wei-chen Lee 蘇順豐 Shun-Feng Su 郭重顯 Chung-Hsien Kuo
學位類別：	碩士 Master
系所名稱：	電資學院 - 電機工程系 Department of Electrical Engineering
論文出版年：	2022
畢業學年度：	110
語文別：	英文
論文頁數：	75
中文關鍵詞：	具容量限制車輛途程問題、基因演算法、強化學習、無人機避障
外文關鍵詞：	Capacitated vehicle routing problem, Genetic Algorithm, Reinforcement Learning, UAV collision avoidance
相關次數：	點閱：195 下載：0
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

無人飛行載具(UAV)，或稱無人機，具有良好的機動性，並隨著導航技術的進步，近年來已經成為包裹配送問題的有效解決方案。在配送包裹時，無人機容易受到電池容量以及載重量的限制，因此必須在解決方案中同時考量運送效率和運輸成本；除此之外還需考量碰撞問題，避免在配送包裹期間和其他無人機相撞。
我們於本文中提出一個無人機配送包裹系統，其中使用了深度強化學習的方式避免無人機之間相撞，並套用基因演算法進行配送路徑的最佳化。具體而言，我們設計的無人機配送包裹系統中會架設一個中央運輸站，負責根據客戶要求設計出近似最佳路線，並將包裹裝載至無人機上，接著每台無人機便會依照分配的路線遞送包裹，同時在過程中避免相互碰撞。
利用深度強化學習(DRL)的方法，我們得以讓各無人機在不曉得其他無人機行進路線的情況下，也可以順利避免相撞。此外，我們採用基因演算法進行最佳化，目標是讓無人機在配送過程中可以有最小的能源消耗。為了得到此種最佳化路徑，我們修改具容量限制車輛途程問題（CVRP）的成本函數，並新增一些新的限制條件；最終我們運用物理引擎進行實際模擬，並透過韌體迴路模擬(SITL)評估本文的研究方法之可行性。

Unmanned Aerial Vehicles (UAVs), or drones, have recently become a favorable solution
for fast parcel delivery due to their maneuverability and advances in navigation technologies.
With the limitation of battery capacity and the payload of drones, it is crucial to consider both efficiency and cost while delivering parcels. Meanwhile, UAVs should not collide with each other while traveling to customers. In this thesis, we propose a UAV parcel delivery system involving deep reinforcement learning approach of collision avoidance and a genetic algorithm for route optimization. Specifically, a centralized distribution center generates near-optimal routes and loads parcels to UAVs according to customer demands, then each UAV takes charge of delivering packages in compliance with the assigned route whilst avoiding collision with each other. We utilize deep reinforcement learning (DRL) to achieve collision avoidance without having prior knowledge about the trajectories of other UAVs. In addition, we adopt genetic algorithm to obtain the lowest minimum energy cost path for each UAV. To find such optimized path, we solve a capacitated vehicle routing problem (CVRP) with modified cost function and extra constraints. Finally, realistic simulations using a physics engine and software-in-the-loop (SITL) are conducted to evaluate the feasibility of the proposed methods.

指導教授推薦書...................................................................................................................................... i
學位考試委員會審定書......................................................................................................................... ii
誌謝 ....................................................................................................................................................... iii
摘要 ....................................................................................................................................................... iv
Abstract .................................................................................................................................................. v
Table of Contents ................................................................................................................................. vi
List of Figures ..................................................................................................................................... viii
List of Tables ......................................................................................................................................... x
Introduction ..................................................................................................................... 1
1.1 Research Background and Motivation .............................................................................. 1
1.2 Literature Review ................................................................................................................ 2
1.2.1 Application of Drones in Parcel Delivery ...................................................................... 2
1.2.2 UAV Collision Avoidance ............................................................................................... 3
1.2.3 Scheduling and Routing Problems for Drone Delivery ............................................... 4
1.3 Organization of the Thesis .................................................................................................. 6
System Architecture and Mechanism ............................................................................ 7
2.1 System Organization ........................................................................................................... 7
2.2 UAV Control Mechanism ................................................................................................. 10
Deep Reinforcement Learning for UAV Collision Avoidance .................................. 13
3.1 Problem Definition ............................................................................................................ 13
3.2 Reinforcement Learning Preliminaries ........................................................................... 13
3.3 State Space ......................................................................................................................... 14
3.4 Action Space ....................................................................................................................... 16
3.5 Reward Function Design ................................................................................................... 17
3.6 Soft Actor Critic Framework in UAV Collision Avoidance Problem ........................... 19
3.7 Training Environment ...................................................................................................... 22
vii
Route Optimization in UAV Parcel Delivery Tasks ................................................... 24
4.1 Cost Function ..................................................................................................................... 24
4.2 Problem Formulation ........................................................................................................ 27
4.3 Adopting Genetic Algorithm ............................................................................................ 29
4.3.1 Chromosome Encoding ................................................................................................. 30
4.3.2 Fitness Function ............................................................................................................ 31
4.3.3 Tournament Selection ................................................................................................... 33
4.3.4 Crossover Operation ..................................................................................................... 33
4.3.5 Mutation Operation ...................................................................................................... 34
Test Results .................................................................................................................... 35
5.1 Validation of UAV Control Mechanism .......................................................................... 35
5.2 Training Results of the Deep Reinforcement Learning based UAV Collision
Avoidance Method .......................................................................................................................... 41
5.3 Validation of the Deep Reinforcement Learning based UAV Collision Avoidance ..... 47
5.4 Test Results of the Genetic Algorithm Based Route Optimization in Simulated Parcel
Delivery System ............................................................................................................................... 50
5.5 Adopting the Proposed Methods in a Simulated Parcel Delivery System .................... 54
Conclusion and Future Works ..................................................................................... 61
Reference ............................................................................................................................................. 62
                                

[1] G. Brockman et al., "Openai gym," arXiv preprint arXiv:1606.01540, 2016.
[2] M. Quigley et al., "ROS: an open-source Robot Operating System," in ICRA workshop
on open source software, 2009, vol. 3, no. 3.2: Kobe, Japan, p. 5.
[3] S. R. R. Singireddy and T. U. Daim, "Technology roadmap: Drone delivery–amazon
prime air," in Infrastructure and technology management: Springer, 2018, pp. 387-412.
[4] I. Hong, M. Kuby, and A. T. Murray, "A range-restricted recharging station coverage
model for drone delivery service planning," Transportation Research Part C: Emerging
Technologies, vol. 90, pp. 198-212, 2018.
[5] S. M. Shavarani, M. G. Nejad, F. Rismanchian, and G. Izbirak, "Application of
hierarchical facility location problem for optimization of a drone delivery system: a
case study of Amazon prime air in the city of San Francisco," The International Journal
of Advanced Manufacturing Technology, vol. 95, no. 9, pp. 3141-3153, 2018.
[6] H. Huang and A. V. Savkin, "Deployment of charging stations for drone delivery
assisted by public transportation vehicles," IEEE Transactions on Intelligent
Transportation Systems, 2021.
[7] D. Wang, P. Hu, J. Du, P. Zhou, T. Deng, and M. Hu, "Routing and scheduling for
hybrid truck-drone collaborative parcel delivery with independent and truck-carried
drones," IEEE Internet of Things Journal, vol. 6, no. 6, pp. 10483-10495, 2019.
[8] D. N. Das, R. Sewani, J. Wang, and M. K. Tiwari, "Synchronized truck and drone
routing in package delivery logistics," IEEE Transactions on Intelligent Transportation
Systems, vol. 22, no. 9, pp. 5772-5782, 2020.
[9] K.-W. Chen, M.-R. Xie, Y.-M. Chen, T.-T. Chu, and Y.-B. Lin, "DroneTalk: An
Internet-of-Things-Based Drone System for Last-Mile Drone Delivery," IEEE
Transactions on Intelligent Transportation Systems, 2022.
[10] K. Loayza, P. Lucas, and E. Peláez, "A centralized control of movements using a
collision avoidance algorithm for a swarm of autonomous agents," in 2017 IEEE
Second Ecuador Technical Chapters Meeting (ETCM), 2017: IEEE, pp. 1-6.

全文公開日期 2024/09/29 (校內網路)
全文公開日期本全文未授權公開 (校外網路)
全文公開日期本全文未授權公開 (國家圖書館：臺灣博碩士論文系統)

簡易檢索 / 詳目顯示

相關論文