臺灣博碩士論文加值系統

本篇論文為一個無人機通訊網路提出了一個強化學習的防撞系統
及最佳路徑規劃。在此網路中，每個無人機在去程時會送貨，回程時
則要收集來自地面上的物聯網裝置的數據。我們採用了強化學習讓一
台無人機在不知道其他無人機路徑的情況下迴避碰撞。此外，對每台
無人機我們使用了最佳化理論去找出一條最短的回程路徑並確保之可
以收集到所有他服務的裝置的數據。為了得到最佳的裝置訪問順序，
我們將此問題想成一個不回原點的旅行銷售員與鄰問題。在給定的訪
問順序下，我們透過解一連串的凸最佳化問題來得到最佳回程路徑。
我們分析並模擬了我們提出的方法。根據模擬結果，我們提出的方法
勝過了一些其他的路徑規劃方法。

In this thesis, we propose a reinforcement learning approach of collision
avoidance and investigate optimal trajectory planning for unmanned aerial
vehicle (UAV) communication networks. Specifically, each UAV takes charge
of delivering objects in the forward path and collecting data from ground
IoT devices in the backward path. We adopt reinforcement learning for
assisting UAVs to learn collision avoidance without knowing the trajectories
of other UAVs in advance. In addition, for each UAV, we use optimization
theory to find out a shortest backward path that assures data collection
from all associated IoT devices. To obtain an optimal visiting order for IoT
devices, we formulate and solve a no-return traveling salesman problem with
neighborhoods (TSPN). Given a visiting order, we formulate and solve a
sequence of convex optimization problems to obtain segments of an optimal
backward path. We use analytical results and simulation results to justify the
usage of the proposed approach. Simulation results show that the proposed
approach is superior to a number of alternative approaches.

Chinese Abstract i
English Abstract ii
Acknowledgements iii
Contents iv
1 Introduction 1
1.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . 4
2 System model and Problem formulation 5
2.1 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Data Collection Model . . . . . . . . . . . . . . . . . . . 6
2.1.2 Collision Avoidance Model . . . . . . . . . . . . . . . . 7
2.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.1 For Data Collection . . . . . . . . . . . . . . . . . . . . 8
2.2.2 For Collision Avoidance . . . . . . . . . . . . . . . . . . 8
3 Trajectory planning algorithm 10
3.1 algorithm we propose . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Description of Q-learning navigation system 23
4.1 Q-learning Environmeant Model . . . . . . . . . . . . . . . . . 24
4.1.1 State Space . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.1.2 Action Space . . . . . . . . . . . . . . . . . . . . . . . . 26
4.1.3 Reward value . . . . . . . . . . . . . . . . . . . . . . . . 27
4.1.4 Validation of our system . . . . . . . . . . . . . . . . . 27
5 Simulation Setup and Results 31
5.1 Data Collection Trajectory Comparison . . . . . . . . . . . . . 32
5.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . 43
6 Conclusion 46
Bibliography 47

[1] Y. Zeng, R. Zhang, and T. J. Lim, “Wireless communications with unmanned aerial
vehicles: opportunities and challenges,＂IEEE Commun. Mag., vol. 54, no. 5, pp. 36–
42, May 2016.
[2] Q. Wu, Y. Zeng, and R. Zhang, “Joint Trajectory and Communication Design for
Multi-UAV Enabled Wireless Networks,＂IEEE Trans. Wireless Commun., vol. 17, no.
3, pp. 2109–2121, Mar. 2018.
[3] Y. Zeng, X. Xu, and R Zhang,“Trajectory Design for Completion Time Minimization
in UAV-Enabled Multicasting,＂IEEE Trans. Wireless Commun., vol. 17, no. 4, pp.
2233–2246, Apr. 2018.
[4] Y. Zeng and R. Zhang, “Energy-efficient UAV communication with trajectory optimization,＂
IEEE Trans. Wirel. Commun., vol. 16, no. 6, pp. 3747–3760, Jun. 2017.
[5] M. Mozaffari, W. Saad, M. Bennis, and M. Debbah, “Mobile Unmanned Aerial Vehicles
(UAVs) for Energy-Efficient Internet of Things Communications,＂IEEE Trans.
Wireless Commun., vol. 16, no. 11, pp. 7574–7589, Nov. 2017.
[6] F. Cheng, S. Zhang, Z. Li, Y. Chen, N. Zhao, F. R. Yu, and V. C. M. Leung, “UAV
Trajectory Optimization for Data Offloading at the Edge of Multiple Cells,＂IEEE
Trans. Veh. Technol., vol. 67, no. 7, pp. 6732–6736, Jul. 2018.
[7] D. Yang, Q. Wu, Y. Zeng, and R. Zhang, “Energy Tradeoff in Ground-to-UAV Communication
via Trajectory Design,＂IEEE Trans. Veh. Technol., vol. 67, no. 7, pp. 6721
–6726, Jul. 2018.
[8] S. Yin, Y. Zhao, and L. Li,“Resource Allocation and Basestation Placement in Cellular
Networks With Wireless Powered UAVs,＂IEEE Trans. Veh. Technol., vol. 68, no. 1,
pp. 1050 - 1055, Jan. 2019.
[9] J. Xu, Y. Zeng, and R. Zhang, “UAV-enabled wireless power transfer: Trajectory
design and energy optimization,＂IEEE Trans. Wireless Commun.,vol. 17, no. 8, pp.
5092 - 5106, Aug. 2018.
[10] E. Bozkaya, and B. Canberk, “BS-on-air: Optimum UAV localization for resilient
ultra dense networks,＂in Proc. IEEE Conference on Computer Communications Workshops
(INFOCOM WKSHPS)., Honolulu, HI, USA, Apr. 2018.
[11] M. Horiuchi, H. Nishiyama, N. Kato, F. Ono, and R. Miura, “Throughput maximization
for long-distance real-time data transmission over multiple UAVs,＂in Proc.
IEEE International Conference on Communications(ICC), May 2016, pp. 1–6.
[12] Z. Chen, X. Zhu, X. Gao, F. Wu, J. Gu, and G. Chen, “Efficient scheduling strategies
for mobile sensors in sweep coverage problem,＂in Proc. IEEE Int. Conf. Sens.,
Commun., Netw. (SECON), Jun. 2016, pp. 1–4.
[13] B. Yuan, M. Orlowska, and S. Sadiq, “On the optimal robot routing problem in
wireless sensor networks,＂IEEE Trans. Knowl. Data Eng., vol. 19, no. 9, pp. 1252–
1261, Sep. 2007.
[14] J. Lyu, Y. Zeng, R. Zhang, and T. J. Lim,“Placement optimization of UAV-mounted
mobile base stations,＂IEEE Commun. Lett., vol. 21, no. 3, pp. 604–607, Mar. 2017.
[15] M. Alzenad, A. El-Keyi, and H. Yanikomeroglu, “3-D placement of an unmanned
aerial vehicle base station for maximum coverage of users with different QoS requirements,＂
IEEE Wireless Commun. Lett., vol. 7, no. 1, pp. 38–41, Feb. 2018.
[16] N. Gageik, P. Benz, and S. Montenegro, ”Obstacle Detection and Collision Avoidance
for a UAV With Complementary Low-Cost Sensors,” in IEEE Access, vol. 3, no. , pp.
599 - 609, May 2015.
[17] Y. Lin and S. Saripalli,｀｀Sampling-based path planning for UAV collision avoidance,＇＇
IEEE Trans. Intell. Transp. Syst., vol. 18, no. 11, pp. 3179–3192, Nov. 2017.
[18] T. T. Mac, C. Copot, A. Hernandez, and R. D. Keyser, “Improved potential field
method for unknown obstacle avoidance using UAV in indoor environment,＂in Proc.
2016 IEEE 14th Int. Symp. Appl. Mach. Intell. Informat., Herl＇any, Slovakia, Jan.
2016, pp. 345–350.
[19] A. Budiyanto, A. Cahyadi, T. B. Adji, and O. Wahyunggoro, “UAV obstacle avoidance
using potential field under dynamic environment,＂in Proc. Int. Conf. Control,
Electron., Renew. Energy Commun. (ICCEREC), Aug. 2015, pp. 187–192.
[20] X. Z. Peng, H. Y. Lin, and J. M. Dai, “Path planning and obstacle avoidance for
vision guided quadrotor UAV navigation,＂in Proc. 2016 12th IEEE Int. Conf. Control
Autom., Kathmandu, Nepal, Jun. 2016, pp. 984–989.
[21] Z. Xu, R. Wei, Q. Zhang, K. Zhou and R. He, “Obstacle avoidance algorithm for
UAVs in unknown environment based on distributional perception and decision making,＂
2016 IEEE Chinese Guidance, Navigation and Control Conference (CGNCC),
Nanjing.CHINA, Aug 2016, pp. 1072-1075.